List of accepted papers for ICALP 2008: TRACK A: Noga Alon and Rani Hod. Optimal Monotone Encodings Liam Roditty and Asaf Shapira. All-Pairs Shortest Paths with a Sublinear Additive Error Oded Regev and Liron Schiff. Impossibility of a Quantum Speed-up with a Faulty Oracle Lior Eldar and Oded Regev. Quantum SAT for a qutrit-cinquit pair is QMA_1-complete Sudipto Guha and Andrew McGregor. Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination Andrei Bulatov. The Complexity of the Counting Constraint Satisfaction Problem Jiri Fiala, Petr Golovach and Jan Kratochvil. Computational complexity of the distance constrained labeling problem for trees Susanne Albers and Sonja Lauer. On List Update with Locality of Reference Sriram Pemmaraju and Aravind Srinivasan. The Randomized Coloring Procedure with Symmetry-Breaking Eli Ben-Sasson, Prahladh Harsha, Oded Lachish and Arie Matsliah. Sound $3$-query PCPPs are Long Satyen Kale and C. Seshadhri. An expansion tester for bounded degree graphs Guy Blelloch, Virginia Vassilevska and Ryan Williams. A New Combinatorial Approach For Sparse Graph Problems Bernhard Haeupler, Kavitha Telikepalli, Matthew Rogers, Siddhartha Sen and Robert E. Tarjan. Topological Ordering Patrick Briest. Uniform Budgets and the Envy-Free Pricing Problem Hans L. Bodlaender, Rod Downey, Michael Fellows and Danny Hermelin. On On Problems Without Polynomial Kernels (Extended Abstract) Yuichi Yoshida and Hiro Ito. Property Testing on $k$-Vertex-Connectivity of Graphs Fedor Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics Feodor Dragan, Fedor Fomin and Petr Golovach. Spanners in sparse graphs Augustin Chaintreau, Pierre Fraigniaud and Emmanuelle Lebhar. Networks become navigable as nodes move and forget Igor Razgon and Barry O'Sullivan. Almost 2-SAT is Fixed-Parameter Tractable (Extended Abstract) Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. The Travelling Salesman Problem in Bounded Degree Graphs Qi Cheng and Daqing Wan. Complexity of Decoding Positive-Rate Reed-Solomon Codes Ioannis Koutis. Faster algebraic algorithms for path and packing problems Gudmund Frandsen and Piotr Sankowski. Dynamic Normal Forms and Dynamic Characteristic Polynomial Jeff Phillips. Algorithms for epsilon-approximations of Terrains David Buchfuhrer and Christopher Umans. The complexity of Boolean formula minimization Alexandr Andoni and Robi Krauthgamer. The Smoothed Complexity of Edit Distance Kousha Etessami, Dominik Wojtczak and Mihalis Yannakakis. Recursive Stochastic Games with Positive Rewards Marco Molinaro and Eduardo Sany Laber. An Approximation Algorithm for Binary Searching in Trees Javier Esparza, Thomas Gawlitza, Stefan Kiefer and Helmut Seidl. Approximative Methods for Monotone Systems of min-max-Polynomial Equations Chen Avin, Michal Koucky and Zvi Lotker. How to Explore a Fast-Changing World Prasad Chebolu, Alan Frieze and Pall Melsted. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time Martin Dietzfelbinger and Rasmus Pagh. Succinct Data Structures for Retrieval and Approximate Membership Iftah Gamzu and Yossi Azar. Truthful Unification Framework for Packing Integer Programs with Choices Andrew Childs and Troy Lee. Optimal quantum adversary lower bounds for ordered search Ken-ichi Kawarabayashi. Approximating list-coloring on a fixed surface David Pritchard. Fast Distributed Computation of Cuts via Random Circulations Krzysztof Onak. Testing Properties of Sets of Points in Metric Spaces Nedialko Dimitrov and C. Greg Plaxton. Competitive Weighted Matching in Transversal Matroids Nikhil Bansal, Ho-Leung Chan, Tak-Wah Lam and Lap-Kei Lee. Scheduling for Speed Bounded Processors Endre Boros, Khaled Elbassioni and Kazuhisa Makino. On Berge Multiplication for Monotone Boolean Dualization Andrei Krokhin and Daniel Marx. On the hardness of losing weight Mehdi Mhalla and Simon Perdrix. Finding Optimal Flows Efficiently Yijia Chen, Marc Thurley and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms Julia Kempe, Oded Regev, Falk Unger and Ronald de Wolf. Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing Chandra Chekuri and Sanjeev Khanna. Algorithms for 2-Route Cut Problems Milan Ruzic. Constructing Efficient Dictionaries in Close to Sorting Time Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond and Shigeru Yamashita. Polynomial-Time Construction of Linear Network Coding Sean Hallgren and Aram Harrow. Superpolynomial speedups based on almost any quantum circuit Ralf Thöle and Klaus Jansen. Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2 Surender Baswana, Akshay Gaur, Sandeep Sen and Jayant Upadhyay. Distance oracles for unweighted graphs : breaking the quadratic barrier with constant additive error Amir Rothschild and Ely Porat. Explicit Non-Adaptive Combinatorial Group Testing Schemes Ilias Diakonikolas, Homin Lee, Kevin Matulef, Rocco Servedio and Andrew Wan. Efficiently Testing Sparse GF(2) Polynomials Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul. Simple, Linear-Time Modular Decomposition Yitong Yin. Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity Detlef Kähler and Thomas Wilke. Complementation, Disambiguation, and Determinization of Büchi Automata Unified Gianluigi Greco and Francesco Scarcello. Tree Projections: Hypergraph Games and Minimality Robert schweller and Ming-Yang Kao. Randomized Self-Assembly for Approximate Shapes Troy Lee and Rajat Mittal. Product theorems via semidefinite programming Dana Glasner, Homin Lee, Tal Malkin, Rocco Servedio, Andrew Wan and Hoeteck Wee. Optimal Cryptographic Hardness of Learning Monotone Functions Friedrich Eisenbrand and Thomas Rothvoss. A Bi-Criteria PTAS for Real-Time Scheduling with Fixed Priorities Ferdinando Cicalese and Eduardo Sany Laber. Function Evaluation via Linear Programming in the Priced Information Model Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu and C. Thach Nguyen. Improved Approximation Algorithms for Budgeted Allocations Michael Schapira, George Christodoulou and Annamaria Kovacs. Bayesian Combinatorial Auctions Flavio Chierichetti and Andrea Vattani. The local nature of list colorings for graphs of high girth Angelo Fanelli, Michele Flammini and Luca Moscardelli. The Speed of Convergence in Congestion Games under Best-Response Dynamics Markus Blaeser, Moritz Hardt and David Steurer. Asymptotically Optimal Hitting Sets Against Polynomials Glencora Borradaile and Philip Klein. The two-edge connectivity survivable network problem in planar graphs Nitin Saxena. Diagonal Circuit Identity Testing and Lower Bounds Greg Plaxton. Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines TRACK B: Manuel Bodirsky and Martin Grohe. Non-dichotomies in Constraint Satisfaction Complexity Tomas Brazdil, Vojtech Forejt and Antonin Kucera. Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives Delia Kesner. Perpetuality for full and safe composition (in a constructive setting) Mikolaj Bojanczyk and Luc Segoufin. Tree languages defined in first-order logic with one quantifier alternation Henrik Björklund and Wim Martens. The Tractability Frontier for NFA Minimization Karin Greimel, Roderick Bloem, Barbara Jobstmann and Moshe Vardi. Open Implication Frédéric Servais and Jean-Francois Raskin. Visibly Pushdown Transducers Patricia Bouyer, Nicolas Markey, Joel Ouaknine and James Worrell. On Expressiveness and Complexity in Real-time Model Checking Matthias Neubauer and Peter Thiemann. Placement Inference for a Client-Server Calculus Vladimeros Vladimerou, Pavithra Prabhakar, Mahesh Viswanathan and Geir Dullerud. STORMED hybrid systems Roland Axelsson, Keijo Heljanko and Martin Lange. Analyzing Context-Free Grammars Using an Incremental SAT Solver Antonio Cano Gomez, Giovanna Guaiana and Jean-Eric Pin. When does partial commutative closure preserve regularity? Shin-ya Katsumata. Attribute Grammars and Categorical Semantics Mai Gehrke, Serge Grigorieff and Jean-Eric Pin. Duality and equational theory of regular languages Hubie Chen. Quantified Constraint Satisfaction and the Polynomially Generated Powers Property Thomas Colcombet and Christof Loeding. The non-deterministic Mostowski hierarchy and distance-parity automata Magnus Johansson, Joachim Parrow, Björn Victor and Jesper Bengtson. Extended pi-Calculi Sven Schewe. ATL* Satisfiability is 2EXPTIME-Complete Bernard Boigelot, Julien Brusten and Véronique Bruyère. On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases Sylvain Lebresne. A System F with exceptions Martin Berger, Kohei Honda and Nobuko Yoshida. Completeness and Logical Full Abstraction in Modal Logics for Typed Mobile Processes Lars Birkedal, Bernhard Reus, Jan Schwinghammer and Hongseok Yang. A Simple Model of Separation Logic for Higher-order Store Robert Simmons and Frank Pfenning. Linear Logical Algorithms Anuj Dawar and Stephan Kreutzer. On Datalog vs. LFP Artur Jez and Alexander Okhotin. On the computational completeness of equations over sets of natural numbers Keye Martin. A domain theoretic model of qubit channels Christian Mathissen. Weighted Logics for Nested Words and Algebraic Formal Power Series Hermann Gruber and Markus Holzer. Finite Automata, Digraph Connectivity, and Regular Expression Size Tomasz Jurdzinski. Leftist Grammars are Nonprimitive Recursive Laszlo Egri, Benoit Larose and Pascal Tesson. Directed ST-Connectivity is not Expressible in Symmetric Datalog Tetsuo Yokoyama, Holger Bock Axelsen and Robert Glück. Reversible Flowchart Languages and the Structured Reversible Program Theorem Bob Coecke and Ross Duncan. Interacting Quantum Observables TRACK C: Universally Composable Undeniable Signature Kaoru Kurosawa and Jun Furukawa Improved Round Complexity for VSS in Point-to-Point Networks Jonathan Katz and Chiu-Yuen Koo and Ranjit Kumaresan The Provable Strength of the Concatenated Hash Combiner when All the Hash Functions are Weak Jonathan J. Hoch and Adi Shamir History-Independent Cuckoo Hashing Moni Naor and Gil Segev and Udi Wieder Building a Collision-Resistant Compression Function from Non-Compressing Primitives Thomas Shrimpton and Martijn Stam Composable Security in the Bounded-Quantum-Storage Model Stephanie Wehner and Juerg Wullschleger Delegating Capabilities in Predicate Encryption Systems Elaine Shi and Brent Waters Constant-Round Concurrent Non-Malleable Zero Knowledge in the Bare Public-Key Model Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti Weak Pseudorandom Functions in Minicrypt Krzysztof Pietrzak and Johan Sjodin Homomorphic Encryption with Chosen-Ciphertext Security Manoj Prabhakaran and Mike Rosulek How to Encrypt with the LPN Problem Henri Gilbert and Matthew J.B. Robshaw and Yannick Seurin Could SFLASH be repaired ? Jintai Ding and Bo-Yin Yang and Chen-Mou Cheng and Owen Chen and Vivien Dubois Interactive PCP Yael Tauman Kalai and Ran Raz Multi-Property Preserving Combiners for Hash Functions Revisited Marc Fischlin and Anja Lehmann and Krzysztof Pietrzak Password Mistyping in Two-Factor-Authenticated Key Exchange Vladimir Kolesnikov and Charles Rackoff Extractable Perfectly One-way Functions Ran Canetti and Ronny R. Dakdouk Asynchronous Multi-Party Computation With Quadratic Communication Martin Hirt and Jesper Buus Nielsen and Bartosz Przydatek Error-Tolerant Combiners for Oblivious Primitives Bartosz Przydatek and Juerg Wullschleger Improved Garbled Circuit: Free XOR Gates and Applications Vladimir Kolesnikov and Thomas Schneider How to Protect Yourself without Perfect Shredding Ran Canetti and Dror Eiger and Shafi Goldwasser and Dah-Yoh Lim On Black-Box Ring Extraction and Integer Factorization Kristina Altmann and Tibor Jager and Andy Rupp Making classical honest verifier zero knowledge protocols secure against quantum attacks Sean Hallgren and Alexandra Kolla and Pranab Sen and Shengyu Zhang Bounded Ciphertext-Policy Attribute based Encryption Vipul Goyal and Abhishek Jain and Omkant Pandey and Amit Sahai Affiliation-Hiding Envelope and Authentication Schemes with Efficient Support for Multiple Affiliations Stanislaw Jarecki and Xiaomin Liu