July 9–13, 2007
Wrocław — Poland
ICALP 2007
34th International Colloquium on
Automata, Languages and Programming
Colocated with LICS 2007, LC 2007, and PPDP 2007

Accepted papers

Track A: Algorithms, Automata, Complexity and Games

  • Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
    Noga Alon, Amin Coja-Oghlan, Hiep Han, Mihyun Kang, Vojtech Rödl and Mathias Schacht
  • Parameterized Algorithms for Directed Maximum Leaf Problems
    Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich and Saket Saurabh
  • Balanced Families of Perfect Hash Functions and Their Applications
    Noga Alon and Shai Gutner
  • On the power of k-consistency
    Albert Atserias, Andrei Bulatov and Victor Dalmau
  • Competitive Algorithms for Due Date Scheduling
    Nikhil Bansal, Kirk Pruhs and Ho-Leung Chan
  • Online conflict-free colorings for hypergraphs
    Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky
  • Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
    Paul Beame, Matei David, Toniann Pitassi and Philipp Woelfel
  • Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
    Andre Berger and Michelangelo Grigni
  • Reconciling data compression and Kolmogorov complexity
    Laurent Bienvenu and Wolfgang Merkle
  • Complexity of the Cover Polynomial
    Markus Bläser and Holger Dell
  • Sampling methods for shortest vectors, closest vectors and successive minima
    Johannes Blömer and Stefanie Naewe
  • On Commutativity Based Edge Lean Search
    Dragan Bosnacki, Edith Elkind, Blaise Genest and Doron Peled
  • Exotic quantifiers, complexity classes, and complete problems
    Peter Buergisser and Felipe Cucker
  • Holographic Algorithms: The Power of Dimensionality Resolved
    Jin-Yi Cai and Pinyan Lu
  • An exponential improvement on the MST heuristic for the Minimum Energy Broadcasting problem
    Ioannis Caragiannis, Michele Flammini and Luca Moscardelli
  • Mechanism design for fractional scheduling on unrelated machines
    George Christodoulou, Elias Koutsoupias and Annamaria Kovacs
  • Checking and Spot-Checking the Correctness of Priority Queues
    Matthew Chu, Sampath Kannan and Andrew McGregor
  • On the Chromatic Number of Random Graphs
    Amin Coja-Oghlan, Konstantinos Panagiotou and Angelika Steger
  • An Optimal Decomposition Algorithm for Tree Edit Distance
    Erik Demaine, Shay Mozes, Benjamin Rossman and Oren Weimann
  • Complexity of Propositional Proofs under a Promise
    Nachum Dershowitz and Iddo Tzameret
  • Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
    Michael Elkin
  • Strong Price of Anarchy for Machine Load Balancing
    Amos Fiat, Haim Kaplan, Meital Levy and Svetlana Olonetsky
  • Distributed Computing with Advice: Information Sensitivity of Graph Coloring
    Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas and Andrzej Pelc
  • In-Place Suffix Sorting
    Gianni Franceschini and S. Muthukrishnan
  • Parameterized Approximability of the Disjoint Cycle Problem
    Martin Grohe and Magdalena Grüber
  • Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
    Sudipto Guha and Andrew McGregor
  • Linear Problem Kernels for NP-Hard Problems on Planar Graphs
    Jiong Guo and Rolf Niedermeier
  • A Framework for Dynamizing Succinct Data Structures
    Ankur Gupta, Wing-Kai Hon, Rahul Shah and Jeffrey Scott Vitter
  • Succinct Ordinal Trees Based on Tree Covering
    Meng He, Ian Munro and S. Srinivasa Rao
  • Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
    Danny Hermelin, Michael Fellows, Guillaume Fertin and Stephane Vialette
  • Unbounded-Error One-Way Classical and Quantum Communication Complexity
    Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita
  • Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
    Irit Katriel, Claire Kenyon and Eli Upfal
  • Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
    Spyros Kontogiannis and Paul Spirakis
  • Labeling Schemes for Vertex Connectivity
    Amos Korman
  • Universal Algebra and Hardness Results for Constraint Satisfaction Problems
    Benoit Larose and Pascal Tesson
  • On the Complexity of Hard-Core Set Constructions
    Chi-Jen Lu, Shi-Chun Tsai and Hsin-Lung Wu
  • A lower bound on entanglement-assisted quantum communication complexity
    Ashley Montanaro and Andreas Winter
  • Estimating Sum by Weighted Sampling
    Rajeev Motwani, Rina Panigrahy and Ying Xu
  • Approximation by DNF: Examples and Counterexamples
    Ryan O'Donnell and Karl Wimmer
  • Low Distortion Spanners
    Seth Pettie
  • Size Competitive Meshing without Large Angles
    Todd Phillips, Don Sheehy and Gary Miller

Track B: Logic, Semantics, and Theory of Programming

  • Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
    Marcelo Arenas, Pablo Barcelo and Leonid Libkin
  • Affine Systems of Equations and Counting Infinitary Logic
    Albert Atserias, Andrei Bulatov and Anuj Dawar
  • Maximal Infinite-Valued Constraint Languages
    Manuel Bodirsky, Hubie Chen, Jan Kara and Timo von Oertzen
  • A Generalization of Cobham's Theorem to Automata over Real Numbers
    Bernard Boigelot and Julien Brusten
  • Bounded depth data trees
    Mikolaj Bojanczyk and Henrik Bjoerklund
  • Decision Problems for lower/upper bound Parametric Timed Automata
    Laura Bozzelli and Salvatore La Torre
  • A combinatorial theorem for trees
    Thomas Colcombet
  • Model theory makes formulas large
    Anuj Dawar, Martin Grohe, Stephan Kreutzer and Nicole Schweikardt
  • Equational Systems and Free Constructions
    Marcelo Fiore and Chung-Kil Hur
  • Perfect information stochastic priority games
    Hugo Gimbert and Wieslaw Zielonka
  • Continuous Capacities on Continuous State Spaces
    Jean Goubault-Larrecq
  • Reachability-time games on timed automata
    Marcin Jurdzinski and Ashutosh Trivedi
  • Unranked Tree Automata with Sibling Equalities and Disequalities
    Wong Karianto and Christof Löding
  • Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the Pi-Calculus
    Naoki Kobayashi and Takashi Suto
  • Boundedness of Monadic FO over Acyclic Structures
    Stephan Kreutzer, Martin Otto and Nicole Schweikardt
  • A Fully Abstract Trace Semantics for General References
    James Laird
  • Aliased Register Allocation for Straight-line Programs is NP-Complete
    Jonathan K. Lee, Jens Palsberg and Fernando Pereira
  • Ready Simulation for Concurrency: It's Logical!
    Gerald Lüttgen and Walter Vogler
  • On the Complexity of LTL Model-Checking of Recursive State
    Gennaro Parlato and Salvatore La Torre
  • Minimum-Time Reachability in Timed Games
    Vinayak Prabhu, Thomas Henzinger, Thomas Brihaye and Jean-Francois Raskin
  • Conservative Ambiguity Detection in Context-Free Grammars
    Sylvain Schmitz
  • Compositional Algorithms for Heterogeneous Modal Logics
    Lutz Schröder and Dirk Pattinson
  • Co-Logic Programming: Extending Logic Programming with Coinduction
    Luke Simon, Ajay Mallya, Ajay Bansal and Gopal Gupta
  • Categorical Views on Computations on Trees
    Tarmo Uustalu, Ichiro Hasuo and Bart Jacobs

Track C: Security and Cryptography Foundations

  • Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms
    Mihir Bellare and Thomas Ristenpart
  • Offline/Online-Mixing
    Ben Adida and Douglas Wikström
  • Unrestricted Aggregate Signatures
    Mihir Bellare and Chanathip Namprempre and Gregory Neven
  • Ring Signatures of Sub-Linear Size without Random Oracles
    Nishanth Chandran and Jens Groth and Amit Sahai
  • Constant-Round Private Database Queries
    Nenad Dedic and Payman Mohassel
  • Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys
    Jun Furukawa and Nuttapong Attrapadung
  • Private Multiparty Sampling and Approximation of Vector Combinations
    Yuval Ishai and Tal Malkin and Martin J. Strauss and Rebecca N. Wright
  • A Characterization of Non-Interactive Instance-Dependent Commitment-Schemes
    Bruce Kapron and Lior Malka and Venkatesh Srinivasan
  • Trading Static for Adaptive Security in Universally Composable Zero-Knowledge
    Aggelos Kiayias and Hong-Sheng Zhou
  • Deterministic History-Independent Strategies for Storing Information on Write-Once Memories
    Tal Moran and Moni Naor and Gil Segev
  • Private Locally Decodable Codes
    Rafail Ostrovsky and Omkant Pandey and Amit Sahai