Automata, Languages and Programming: 35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008 Proceedings, Part I (Lecture Notes in Computer Science (5125))

Annotation 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 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 - Annotation 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 5126 contains 56 contributions of track B and track C selected from 208 submissions and 2 invited lectures. The papers for track B are organized in topical sections on bounds, distributed computation, real-time and probabilistic systems, logic and complexity, words and trees, nonstandard models of computation, reasoning about computation, and verification. The papers of track C cover topics in security and cryptography such as theory, secure computation, two-party protocols and zero-knowledge, encryption with special properties/quantum cryptography, various types of hashing, as well as public-key cryptography and authentication