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

The two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008.

The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing.

---

The two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008.

The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing.

---

The two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008.

The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing.

Content:
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
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
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
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation....Pages 246-257
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
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
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
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
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
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
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
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
Superpolynomial Speedups Based on Almost Any Quantum Circuit ....Pages 881-892
Back Matter....Pages E1-E2
....Pages -