• 
  Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener (Eds.): Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I. Springer 2006 Lecture Notes in Computer Science ISBN 3-540-35904-4

Invited Lectures

• 
  Noga Alon, Asaf Shapira, Benny Sudakov: Additive Approximation for Edge-Deletion Problems (Abstract). 1-2

Graph Theory I

• 
  Martin Grohe, Oleg Verbitsky: Testing Graph Isomorphism in Parallel by Playing a Game. 3-14
• 
  Amin Coja-Oghlan, André Lanka: The Spectral Gap of Random Graphs with Given Expected Degrees. 15-26
• 
  Douglas E. Carroll, Ashish Goel, Adam Meyerson: Embedding Bounded Bandwidth Graphs into l₁. 27-37
• 
  Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On Counting Homomorphisms to Directed Acyclic Graphs. 38-49

Quantum Computing

• 
  Ben Reichardt: Fault-Tolerance Threshold for a Distance-Three Quantum Code. 50-61
• 
  Ronald de Wolf: Lower Bounds on Matrix Rigidity Via a Quantum Argument. 62-71
• 
  Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier: Self-testing of Quantum Circuits. 72-83

Randomness

• 
  Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai: Deterministic Extractors for Independent-Symbol Sources. 84-95
• 
  Jaikumar Radhakrishnan: Gap Amplification in PCPs Using Lazy Random Walks. 96-107
• 
  Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Stopping Times, Metrics and Approximate Counting. 108-119

Formal Languages

• 
  Michal Kunc: Algebraic Characterization of the Finite Power Property. 120-131
• 
  Turlough Neary, Damien Woods: P-completeness of Cellular Automaton Rule 110. 132-143
• 
  Christos A. Kapoutsis: Small Sweeping 2NFAs Are Not Closed Under Complement. 144-156
• 
  Mikolaj Bojanczyk, Mathias Samuelides, Thomas Schwentick, Luc Segoufin: Expressive Power of Pebble Automata. 157-168

Approximation Algorithms I

• 
  R. Ravi, Mohit Singh: Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs. 169-180
• 
  Naveen Garg, Amit Kumar: Better Algorithms for Minimizing Average Flow-Time on Related Machines. 181-190
• 
  Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: A Push-Relabel Algorithm for Approximating Degree Bounded MSTs. 191-201
• 
  Satish Rao, Shuheng Zhou: Edge Disjoint Paths in Moderately Connected Graphs. 202-213

Approximation Algorithms II

• 
  Leah Epstein, Asaf Levin: A Robust APTAS for the Classical Bin Packing Problem. 214-225
• 
  Subhash Khot, Ashok Kumar Ponnuswami: Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. 226-237
• 
  Rolf Harren: Approximating the Orthogonal Knapsack Problem for Hypercubes. 238-249

Graph Algorithms I

• 
  Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn: A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs. 250-261
• 
  Virginia Vassilevska, Ryan Williams, Raphael Yuster: Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. 262-273
• 
  Piotr Sankowski: Weighted Bipartite Matching in Matrix Multiplication Time. 274-285

Algorithms I

• 
  Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano: Optimal Resilient Sorting and Searching in the Presence of Memory Faults. 286-298
• 
  Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff: Reliable and Efficient Computational Geometry Via Controlled Perturbation. 299-310
• 
  Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, Luca Moscardelli: Tight Bounds for Selfish and Greedy Load Balancing. 311-322

Complexity I

• 
  Arist Kojevnikov, Dmitry Itsykson: Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. 323-334
• 
  Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. 335-345
• 
  Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 346-357

Data Structures and Linear Algebra

• 
  Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein: Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. 358-369
• 
  Alexander Golynski: Optimal Lower Bounds for Rank and Select Indexes. 370-381
• 
  Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas, Christos D. Zaroliagis: Dynamic Interpolation Search Revisited. 382-394
• 
  Gudmund Skovbjerg Frandsen, Peter Frands Frandsen: Dynamic Matrix Rank. 395-406

Graphs

• 
  Xin He, Huaming Zhang: Nearly Optimal Visibility Representations of Plane Graphs. 407-418
• 
  Hristo Djidjev, Imrich Vrto: Planar Crossing Numbers of Genus g Graphs. 419-430
• 
  Toshihiro Fujito: How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. 431-442
• 
  Guy Kortsarz, Zeev Nutov: Tight Approximation Algorithm for Connectivity Augmentation Problems. 443-452

Complexity II

• 
  Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf: On the Bipartite Unique Perfect Matching Problem. 453-464
• 
  John M. Hitchcock, Aduri Pavan: Comparing Reductions to NP-Complete Sets. 465-476
• 
  Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani: Design Is as Easy as Optimization. 477-488
• 
  Xi Chen, Xiaotie Deng: On the Complexity of 2D Discrete Fixed Point Problem. 489-500

Game Theory I

• 
  Martin Gairing, Burkhard Monien, Karsten Tiemann: Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. 501-512
• 
  Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou: The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. 513-524
• 
  Roberto Cominetti, José R. Correa, Nicolás E. Stier Moses: Network Games with Atomic Players. 525-536

Algorithms II

• 
  David Doty, Jack H. Lutz, Satyadev Nandakumar: Finite-State Dimension and Real Arithmetic. 537-547
• 
  Andreas Björklund, Thore Husfeldt: Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. 548-559
• 
  Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini: The Myriad Virtues of Wavelet Trees. 560-571

Game Theory II

• 
  Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis: Atomic Congestion Games Among Coalitions. 572-583
• 
  Bruno Codenotti, Luis Rademacher, Kasturi R. Varadarajan: Computing Equilibrium Prices in Exchange Economies with Tax Distortions. 584-595
• 
  Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano, Carmine Ventre: New Constructions of Mechanisms with Verification. 596-607

Networks, Circuits and Regular Expressions

• 
  Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo: On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. 608-618
• 
  Amos Korman, David Peleg: Dynamic Routing Schemes for General Graphs. 619-630
• 
  Kei Uchizawa, Rodney J. Douglas, Wolfgang Maass: Energy Complexity and Entropy of Threshold Circuits. 631-642
• 
  Philip Bille: New Algorithms for Regular Expression Matching. 643-654

Fixed Parameter Complexity and Approximation Algorithms

• 
  Dániel Marx: A Parameterized View on Matroid Optimization Problems. 655-666
• 
  Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar: Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction. 667-678
• 
  Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, Martin Skutella: Length-Bounded Cuts and Flows. 679-690

Graph Algorithms II

• 
  Amin Coja-Oghlan: An Adaptive Spectral Heuristic for Partitioning Random Graphs. 691-702
• 
  Jin-yi Cai, Vinay Choudhary: Some Results on Matchgates and Holographic Algorithms. 703-714
• 
  Julián Mestre: Weighted Popular Matchings. 715-726