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

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 -