List of accepted papers for ICALP 2007: TRACK A: An Optimal Decomposition Algorithm for Tree Edit Distance Erik Demaine, Shay Mozes, Benjamin Rossman and Oren Weimann. Exotic quantifiers, complexity classes, and complete problems Peter Buergisser and Felipe Cucker. Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners Michael Elkin. A lower bound on entanglement-assisted quantum communication complexity Ashley Montanaro and Andreas Winter. Labeling Schemes for Vertex Connectivity Amos Korman. On Cover Time vs. Randomized Broadcasting Thomas Sauerwald and Robert Elsasser. Holographic Algorithms: The Power of Dimensionality Resolved Jin-Yi Cai and Pinyan Lu. Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games Spyros Kontogiannis and Paul Spirakis. Complexity of Propositional Proofs under a Promise Nachum Dershowitz and Iddo Tzameret. Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs Danny Hermelin, Michael Fellows, Guillaume Fertin and Stephane Vialette. Online conflict-free colorings for hypergraphs Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky. Competitive Algorithms for Due Date Scheduling Nikhil Bansal, Kirk Pruhs and Ho-Leung Chan. Balanced Families of Perfect Hash Functions and Their Applications Noga Alon and Shai Gutner. Distributed Computing with Advice: Information Sensitivity of Graph Coloring Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas and Andrzej Pelc. On the Complexity of Hard-Core Set Constructions Chi-Jen Lu, Shi-Chun Tsai and Hsin-Lung Wu. Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions Alon Noga, Amin Coja-Oghlan, Hiep Han, Mihyun Kang, Vojtech Rodl and Mathias Schacht. Parameterized Algorithms for Directed Maximum Leaf Problems Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich and Saket Saurabh. Succinct Ordinal Trees Based on Tree Covering Meng He, Ian Munro and S. Srinivasa Rao. Low Distortion Spanners Seth Pettie. Universal Algebra and Hardness Results for Constraint Satisfaction Problems Benoit Larose and Pascal Tesson. Estimating Sum by Weighted Sampling Rajeev Motwani, Rina Panigrahy and Ying Xu. Minimum Weight 2-Edge-Connected Spanning Subgraphs Andre Berger and Michelangelo Grigni. On Commutativity Based Edge Lean Search Dragan Bosnacki, Edith Elkind, Blaise Genest and Doron Peled. Unbounded-Error One-Way Classical and Quantum Communication Complexity Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita. Mechanism design for fractional scheduling on unrelated machines George Christodoulou, Elias Koutsoupias and Annamaria Kovacs. In-Place Suffix Sorting Gianni Franceschini and S. Muthukrishnan. Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity Paul Beame, Matei David, Toniann Pitassi and Philipp Woelfel. Reconciling data compression and Kolmogorov complexity Laurent Bienvenu and Wolfgang Merkle. Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming Sudipto Guha and Andrew McGregor. Parameterized Approximability of the Disjoint Cycle Problem Martin Grohe and Magdalena Gruber. 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. Complexity of the Cover Polynomial Markus Blaser and Holger Dell. On the power of k-consistency Albert Atserias, Andrei Bulatov and Victor Dalmau. Sampling methods for shortest vectors, closest vectors and successive minima Johannes Blomer and Stefanie Naewe. Size Competitive Meshing without Large Angles Todd Phillips, Don Sheehy and Gary Miller. Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems Irit Katriel, Claire Kenyon and Eli Upfal. A Framework for Dynamizing Succinct Data Structures Ankur Gupta, Wing-Kai Hon, Rahul Shah and Jeffrey Scott Vitter. Approximation by DNF: Examples and Counterexamples Ryan O'Donnell and Karl Wimmer. Strong Price of Anarchy for Machine Load Balancing Amos Fiat, Haim Kaplan, Meital Levy and Svetlana Olonetsky. Linear Problem Kernels for NP-Hard Problems on Planar Graphs Jiong Guo and Rolf Niedermeier. An exponential improvement on the MST heuristic for the Minimum Energy Broadcasting problem Ioannis Caragiannis, Michele Flammini and Luca Moscardelli. TRACK B: 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 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: Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys Jun Furukawa and Nuttapong Attrapadung Constant-Round Private Database Queries Nenad Dedic and Payman Mohassel Unrestricted Aggregate Signatures Mihir Bellare and Chanathip Namprempre and Gregory Neven 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 A Characterization of Non-Interactive Instance-Dependent Commitment-Schemes Bruce Kapron and Lior Malka and Venkatesh Srinivasan Offline/Online-Mixing Ben Adida and Douglas Wikström Trading Static for Adaptive Security in Universally Composable Zero-Knowledge Aggelos Kiayias and Hong-Sheng Zhou Private Multiparty Sampling and Approximation of Vector Combinations Yuval Ishai and Tal Malkin and Martin J. Strauss and Rebecca N. Wright Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms Mihir Bellare and Thomas Ristenpart Ring Signatures of Sub-Linear Size without Random Oracles Nishanth Chandran and Jens Groth and Amit Sahai