Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I

Noga Alon, Asaf Shapira, Benny Sudakov (auth.), Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener (eds.)3540359044, 9783540359043

The two-volume set LNCS 4051 and LNCS 4052 constitutes the refereed proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, held in Venice, Italy, in July 2006.

This is Volume I (LNCS 4051), presenting 61 revised full papers together with 1 invited lecture that were carefully reviewed and selected from 230 submissions. Those papers have a special focus on algorithms, automata, complexity and games and are organized in topical sections on graph theory, quantum computing, randomness, formal languages, approximation algorithms, graph algorithms, algorithms, complexity, data structures and linear algebra, graphs, game theory, networks, circuits and regular expressions, fixed parameter complexity and approximation algorithms.

Volume II (LNCS 4052) comprises 2 invited papers and 2 additional conference tracks with 24 papers each – rigorously selected from numerous submissions – focusing on algorithms, automata, complexity and games as well as on security and cryptography foundation respectively. The papers are organized in topical sections on zero-knowledge and signatures, cryptographic protocols, secrecy

---

Table of contents :
Front Matter….Pages –
Additive Approximation for Edge-Deletion Problems (Abstract)….Pages 1-2
Testing Graph Isomorphism in Parallel by Playing a Game….Pages 3-14
The Spectral Gap of Random Graphs with Given Expected Degrees….Pages 15-26
Embedding Bounded Bandwidth Graphs into ℓ 1 ….Pages 27-37
On Counting Homomorphisms to Directed Acyclic Graphs….Pages 38-49
Fault-Tolerance Threshold for a Distance-Three Quantum Code….Pages 50-61
Lower Bounds on Matrix Rigidity Via a Quantum Argument….Pages 62-71
Self-testing of Quantum Circuits….Pages 72-83
Deterministic Extractors for Independent-Symbol Sources….Pages 84-95
Gap Amplification in PCPs Using Lazy Random Walks….Pages 96-107
Stopping Times, Metrics and Approximate Counting….Pages 108-119
Algebraic Characterization of the Finite Power Property….Pages 120-131
P-completeness of Cellular Automaton Rule 110….Pages 132-143
Small Sweeping 2NFAs Are Not Closed Under Complement….Pages 144-156
Expressive Power of Pebble Automata….Pages 157-168
Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs….Pages 169-180
Better Algorithms for Minimizing Average Flow-Time on Related Machines….Pages 181-190
A Push-Relabel Algorithm for Approximating Degree Bounded MSTs….Pages 191-201
Edge Disjoint Paths in Moderately Connected Graphs….Pages 202-213
A Robust APTAS for the Classical Bin Packing Problem….Pages 214-225
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion….Pages 226-237
Approximating the Orthogonal Knapsack Problem for Hypercubes….Pages 238-249
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs….Pages 250-261
Finding the Smallest H -Subgraph in Real Weighted Graphs and Related Problems….Pages 262-273
Weighted Bipartite Matching in Matrix Multiplication Time….Pages 274-285
Optimal Resilient Sorting and Searching in the Presence of Memory Faults….Pages 286-298
Reliable and Efficient Computational Geometry Via Controlled Perturbation….Pages 299-310
Tight Bounds for Selfish and Greedy Load Balancing….Pages 311-322
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies….Pages 323-334
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws….Pages 335-345
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies….Pages 346-357
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing….Pages 358-369
Optimal Lower Bounds for Rank and Select Indexes….Pages 370-381
Dynamic Interpolation Search Revisited….Pages 382-394
Dynamic Matrix Rank….Pages 395-406
Nearly Optimal Visibility Representations of Plane Graphs….Pages 407-418
Planar Crossing Numbers of Genus g Graphs….Pages 419-430
How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover….Pages 431-442
Tight Approximation Algorithm for Connectivity Augmentation Problems….Pages 443-452
On the Bipartite Unique Perfect Matching Problem….Pages 453-464
Comparing Reductions to NP-Complete Sets….Pages 465-476
Design Is as Easy as Optimization….Pages 477-488
On the Complexity of 2D Discrete Fixed Point Problem….Pages 489-500
Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions….Pages 501-512
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games….Pages 513-524
Network Games with Atomic Players….Pages 525-536
Finite-State Dimension and Real Arithmetic….Pages 537-547
Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings….Pages 548-559
The Myriad Virtues of Wavelet Trees….Pages 560-571
Atomic Congestion Games Among Coalitions….Pages 572-583
Computing Equilibrium Prices in Exchange Economies with Tax Distortions….Pages 584-595
New Constructions of Mechanisms with Verification….Pages 596-607
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations….Pages 608-618
Dynamic Routing Schemes for General Graphs….Pages 619-630
Energy Complexity and Entropy of Threshold Circuits….Pages 631-642
New Algorithms for Regular Expression Matching….Pages 643-654
A Parameterized View on Matroid Optimization Problems….Pages 655-666
Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction….Pages 667-678
Length-Bounded Cuts and Flows….Pages 679-690
An Adaptive Spectral Heuristic for Partitioning Random Graphs….Pages 691-702
Some Results on Matchgates and Holographic Algorithms….Pages 703-714
Weighted Popular Matchings….Pages 715-726
Back Matter….Pages –