Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I

Front Matter....Pages -
Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects....Pages 1-13
Internet Ad Auctions: Insights and Directions....Pages 14-23
Function Evaluation Via Linear Programming in the Priced Information Model....Pages 173-185
Improved Approximation Algorithms for Budgeted Allocations....Pages 186-197
The Travelling Salesman Problem in Bounded Degree Graphs....Pages 198-209
Treewidth Computation and Extremal Combinatorics....Pages 210-221
Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines....Pages 222-233
Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2....Pages 234-245
The Complexity of Boolean Formula Minimization....Pages 24-35
Optimal Cryptographic Hardness of Learning Monotone Functions....Pages 36-47
On Berge Multiplication for Monotone Boolean Dualization....Pages 48-59
Diagonal Circuit Identity Testing and Lower Bounds....Pages 60-71
Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity....Pages 72-83
Constructing Efficient Dictionaries in Close to Sorting Time....Pages 84-95
On List Update with Locality of Reference....Pages 96-107
A New Combinatorial Approach for Sparse Graph Problems....Pages 108-120
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)....Pages 121-132
Networks Become Navigable as Nodes Move and Forget....Pages 133-144
Fast Distributed Computation of Cuts Via Random Circulations....Pages 145-160
Finding a Maximum Matching in a Sparse Random Graph in O ( n ) Expected Time....Pages 161-172
Asymptotically Optimal Hitting Sets Against Polynomials....Pages 345-356
The Smoothed Complexity of Edit Distance....Pages 357-369
Randomized Self-assembly for Approximate Shapes....Pages 370-384
Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)....Pages 385-396
Competitive Weighted Matching in Transversal Matroids....Pages 397-408
Scheduling for Speed Bounded Processors....Pages 409-420
Faster Algorithms for Incremental Topological Ordering....Pages 421-433
Dynamic Normal Forms and Dynamic Characteristic Polynomial....Pages 434-446
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation....Pages 246-257
Algorithms for ε -Approximations of Terrains....Pages 447-458
An Approximation Algorithm for Binary Searching in Trees....Pages 459-471
Algorithms for 2-Route Cut Problems....Pages 472-484
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs....Pages 485-501
Optimal Monotone Encodings....Pages 258-270
Polynomial-Time Construction of Linear Network Coding....Pages 271-282
Complexity of Decoding Positive-Rate Reed-Solomon Codes....Pages 283-293
Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)....Pages 294-305
The Randomized Coloring Procedure with Symmetry-Breaking....Pages 306-319
The Local Nature of List Colorings for Graphs of High Girth....Pages 320-332
Approximating List-Coloring on a Fixed Surface....Pages 333-344
Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)....Pages 551-562
On Problems without Polynomial Kernels (Extended Abstract)....Pages 563-574
Faster Algebraic Algorithms for Path and Packing Problems....Pages 575-586
Understanding the Complexity of Induced Subgraph Isomorphisms....Pages 587-596
Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations....Pages 698-710
Recursive Stochastic Games with Positive Rewards....Pages 711-723
Complementation, Disambiguation, and Determinization of Büchi Automata Unified....Pages 724-735
Tree Projections: Hypergraph Games and Minimality....Pages 736-747
Efficiently Testing Sparse GF (2) Polynomials....Pages 502-514
Testing Properties of Sets of Points in Metric Spaces....Pages 515-526
An Expansion Tester for Bounded Degree Graphs....Pages 527-538
Property Testing on k -Vertex-Connectivity of Graphs....Pages 539-550
Spanners in Sparse Graphs....Pages 597-608
Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error....Pages 609-621
All-Pairs Shortest Paths with a Sublinear Additive Error....Pages 622-633
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations....Pages 634-645
The Complexity of the Counting Constraint Satisfaction Problem....Pages 646-661
On the Hardness of Losing Weight....Pages 662-673
Product Theorems Via Semidefinite Programming....Pages 674-685
Sound 3-Query PCPPs Are Long....Pages 686-697
Explicit Non-adaptive Combinatorial Group Testing Schemes....Pages 748-759
Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination....Pages 760-772
Impossibility of a Quantum Speed-Up with a Faulty Oracle....Pages 773-781
Superpolynomial Speedups Based on Almost Any Quantum Circuit....Pages 782-795
The Speed of Convergence in Congestion Games under Best-Response Dynamics....Pages 796-807
Uniform Budgets and the Envy-Free Pricing Problem....Pages 808-819
Bayesian Combinatorial Auctions....Pages 820-832
Truthful Unification Framework for Packing Integer Programs with Choices....Pages 833-844
Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing....Pages 845-856
Finding Optimal Flows Efficiently....Pages 857-868
Optimal Quantum Adversary Lower Bounds for Ordered Search....Pages 869-880
Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1 -Complete....Pages 881-892
Superpolynomial Speedups Based on Almost Any Quantum Circuit....Pages E1-E2
Back Matter....Pages -