• 
  Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz (Eds.): Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. Springer 2008 Lecture Notes in Computer Science ISBN 978-3-540-70574-1

Invited Lectures

• 
  Bruno Courcelle: Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects. 1-13
• 
  S. Muthukrishnan: Internet Ad Auctions: Insights and Directions. 14-23

Complexity: Boolean Functions and Circuits

• 
  David Buchfuhrer, Christopher Umans: The Complexity of Boolean Formula Minimization. 24-35
• 
  Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee: Optimal Cryptographic Hardness of Learning Monotone Functions. 36-47
• 
  Endre Boros, Khaled M. Elbassioni, Kazuhisa Makino: On Berge Multiplication for Monotone Boolean Dualization. 48-59
• 
  Nitin Saxena: Diagonal Circuit Identity Testing and Lower Bounds. 60-71

Data Structures

• 
  Yitong Yin: Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity. 72-83
• 
  Milan Ruzic: Constructing Efficient Dictionaries in Close to Sorting Time. 84-95
• 
  Susanne Albers, Sonja Lauer: On List Update with Locality of Reference. 96-107
• 
  Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: A New Combinatorial Approach for Sparse Graph Problems. 108-120

Random Walks and Random Structures

• 
  Chen Avin, Michal Koucký, Zvi Lotker: How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). 121-132
• 
  Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar: Networks Become Navigable as Nodes Move and Forget. 133-144
• 
  David Pritchard: Fast Distributed Computation of Cuts Via Random Circulations. 145-160
• 
  Prasad Chebolu, Alan M. Frieze, Páll Melsted: Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. 161-172

Design and Analysis of Algorithms

• 
  Ferdinando Cicalese, Eduardo Sany Laber: Function Evaluation Via Linear Programming in the Priced Information Model. 173-185
• 
  Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen: Improved Approximation Algorithms for Budgeted Allocations. 186-197
• 
  Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto: The Travelling Salesman Problem in Bounded Degree Graphs. 198-209
• 
  Fedor V. Fomin, Yngve Villanger: Treewidth Computation and Extremal Combinatorics. 210-221

Scheduling

• 
  C. Greg Plaxton: Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines. 222-233
• 
  Klaus Jansen, Ralf Thöle: Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2. 234-245
• 
  Friedrich Eisenbrand, Thomas Rothvoß: A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. 246-257

Codes and Coding

• 
  Noga Alon, Rani Hod: Optimal Monotone Encodings. 258-270
• 
  Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita: Polynomial-Time Construction of Linear Network Coding. 271-282
• 
  Qi Cheng, Daqing Wan: Complexity of Decoding Positive-Rate Reed-Solomon Codes. 283-293

Coloring

• 
  Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract). 294-305
• 
  Sriram V. Pemmaraju, Aravind Srinivasan: The Randomized Coloring Procedure with Symmetry-Breaking. 306-319
• 
  Flavio Chierichetti, Andrea Vattani: The Local Nature of List Colorings for Graphs of High Girth. 320-332
• 
  Ken-ichi Kawarabayashi: Approximating List-Coloring on a Fixed Surface. 333-344

Randomness in Computation

• 
  Markus Bläser, Moritz Hardt, David Steurer: Asymptotically Optimal Hitting Sets Against Polynomials. 345-356
• 
  Alexandr Andoni, Robert Krauthgamer: The Smoothed Complexity of Edit Distance. 357-369
• 
  Ming-Yang Kao, Robert T. Schweller: Randomized Self-assembly for Approximate Shapes. 370-384
• 
  Martin Dietzfelbinger, Rasmus Pagh: Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract). 385-396

Online and Dynamic Algorithms

• 
  Nedialko B. Dimitrov, C. Greg Plaxton: Competitive Weighted Matching in Transversal Matroids. 397-408
• 
  Nikhil Bansal, Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee: Scheduling for Speed Bounded Processors. 409-420
• 
  Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan: Faster Algorithms for Incremental Topological Ordering. 421-433
• 
  Gudmund Skovbjerg Frandsen, Piotr Sankowski: Dynamic Normal Forms and Dynamic Characteristic Polynomial. 434-446

Approximation Algorithms

• 
  Jeff M. Phillips: Algorithms for epsilon-Approximations of Terrains. 447-458
• 
  Eduardo Sany Laber, Marco Molinaro: An Approximation Algorithm for Binary Searching in Trees. 459-471
• 
  Chandra Chekuri, Sanjeev Khanna: Algorithms for 2-Route Cut Problems. 472-484
• 
  Glencora Borradaile, Philip N. Klein: The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. 485-501

Property Testing

• 
  Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan: Efficiently Testing Sparse GF(2) Polynomials. 502-514
• 
  Krzysztof Onak: Testing Properties of Sets of Points in Metric Spaces. 515-526
• 
  Satyen Kale, C. Seshadhri: An Expansion Tester for Bounded Degree Graphs. 527-538
• 
  Yuichi Yoshida, Hiro Ito: Property Testing on k-Vertex-Connectivity of Graphs. 539-550

Parameterized Algorithms and Complexity

• 
  Igor Razgon, Barry O'Sullivan: Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). 551-562
• 
  Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On Problems without Polynomial Kernels (Extended Abstract). 563-574
• 
  Ioannis Koutis: Faster Algebraic Algorithms for Path and Packing Problems. 575-586
• 
  Yijia Chen, Marc Thurley, Mark Weyer: Understanding the Complexity of Induced Subgraph Isomorphisms. 587-596

Graph Algorithms

• 
  Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach: Spanners in Sparse Graphs. 597-608
• 
  Surender Baswana, Akshay Gaur, Sandeep Sen, Jayant Upadhyay: Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error. 609-621
• 
  Liam Roditty, Asaf Shapira: All-Pairs Shortest Paths with a Sublinear Additive Error. 622-633
• 
  Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. 634-645

Computational Complexity

• 
  Andrei A. Bulatov: The Complexity of the Counting Constraint Satisfaction Problem. 646-661
• 
  Andrei A. Krokhin, Dániel Marx: On the Hardness of Losing Weight. 662-673
• 
  Troy Lee, Rajat Mittal: Product Theorems Via Semidefinite Programming. 674-685
• 
  Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah: Sound 3-Query PCPPs Are Long. 686-697

Games and Automata

• 
  Javier Esparza, Thomas Gawlitza, Stefan Kiefer, Helmut Seidl: Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations. 698-710
• 
  Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis: Recursive Stochastic Games with Positive Rewards. 711-723
• 
  Detlef Kähler, Thomas Wilke: Complementation, Disambiguation, and Determinization of Büchi Automata Unified. 724-735
• 
  Gianluigi Greco, Francesco Scarcello: Tree Projections: Hypergraph Games and Minimality. 736-747

Group Testing, Streaming, and Quantum

• 
  Ely Porat, Amir Rothschild: Explicit Non-adaptive Combinatorial Group Testing Schemes. 748-759
• 
  Sudipto Guha, Andrew McGregor: Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination. 760-772
• 
  Oded Regev, Liron Schiff: Impossibility of a Quantum Speed-Up with a Faulty Oracle. 773-781
• 
  Sean Hallgren, Aram Wettroth Harrow: Superpolynomial Speedups Based on Almost Any Quantum Circuit. 782-795

Algorithmic Game Theory

• 
  Angelo Fanelli, Michele Flammini, Luca Moscardelli: The Speed of Convergence in Congestion Games under Best-Response Dynamics. 796-807
• 
  Patrick Briest: Uniform Budgets and the Envy-Free Pricing Problem. 808-819
• 
  George Christodoulou, Annamária Kovács, Michael Schapira: Bayesian Combinatorial Auctions. 820-832
• 
  Yossi Azar, Iftah Gamzu: Truthful Unification Framework for Packing Integer Programs with Choices. 833-844

Quantum

• 
  Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. 845-856
• 
  Mehdi Mhalla, Simon Perdrix: Finding Optimal Flows Efficiently. 857-868
• 
  Andrew M. Childs, Troy Lee: Optimal Quantum Adversary Lower Bounds for Ordered Search. 869-880
• 
  Lior Eldar, Oded Regev: Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. 881-892