33. ICALP 2006: Venice, Italy

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. Lecture Notes in Computer Science 4051 Springer 2006, ISBN 3-540-35904-4 BibTeX

Invited Lectures

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

Graph Theory I

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

Quantum Computing

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

Randomness

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

Formal Languages

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

Approximation Algorithms I

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

Approximation Algorithms II

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

Graph Algorithms I

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

Algorithms I

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

Complexity I

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

Data Structures and Linear Algebra

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

Graphs

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

Complexity II

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

Game Theory I

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

Algorithms II

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

Game Theory II

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

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
Electronic Edition (link) BibTeX
Amos Korman, David Peleg:
Dynamic Routing Schemes for General Graphs. 619-630
Electronic Edition (link) BibTeX
Kei Uchizawa, Rodney J. Douglas, Wolfgang Maass:
Energy Complexity and Entropy of Threshold Circuits. 631-642
Electronic Edition (link) BibTeX
Philip Bille:
New Algorithms for Regular Expression Matching. 643-654
Electronic Edition (link) BibTeX

Fixed Parameter Complexity and Approximation Algorithms

Dániel Marx:
A Parameterized View on Matroid Optimization Problems. 655-666
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, Martin Skutella:
Length-Bounded Cuts and Flows. 679-690
Electronic Edition (link) BibTeX

Graph Algorithms II

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