Ebook: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers presented were carefully reviewed and selected from 422 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.

---

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers presented were carefully reviewed and selected from 422 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.

---

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers presented were carefully reviewed and selected from 422 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.
Content:
Front Matter....Pages -
Exact Weight Subgraphs and the k-Sum Conjecture....Pages 1-12
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines....Pages 13-24
Tight Lower Bound for Linear Sketches of Moments....Pages 25-32
Optimal Partitioning for Dual Pivot Quicksort....Pages 33-44
Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm....Pages 45-56
On the Extension Complexity of Combinatorial Polytopes....Pages 57-68
Algorithms for Hub Label Optimization....Pages 69-80
Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems....Pages 81-92
Search-Space Size in Contraction Hierarchies....Pages 93-104
Time-Efficient Quantum Walks for 3-Distinctness....Pages 105-122
An Algebraic Characterization of Testable Boolean CSPs....Pages 123-134
Approximation Algorithms for the Joint Replenishment Problem with Deadlines....Pages 135-147
Sparse Suffix Tree Construction in Small Space....Pages 148-159
Tree Compression with Top Trees....Pages 160-171
Noncommutativity Makes Determinants Hard....Pages 172-183
Optimal Orthogonal Graph Drawing with Convex Bend Costs....Pages 184-195
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth....Pages 196-207
On the Complexity of Higher Order Abstract Voronoi Diagrams....Pages 208-219
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions....Pages 220-231
Direct Product via Round-Preserving Compression....Pages 232-243
How Hard Is Counting Triangles in the Streaming Model?....Pages 244-254
Online Checkpointing with Improved Worst-Case Guarantees....Pages 255-266
Exact and Efficient Generation of Geometric Random Variates and Random Graphs....Pages 267-278
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm....Pages 279-290
On Randomized Online Labeling with Polynomially Many Labels....Pages 291-302
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities....Pages 303-314
New Doubling Spanners: Better and Simpler....Pages 315-327
Maximum Edge-Disjoint Paths in k-Sums of Graphs....Pages 328-339
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy....Pages 340-351
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree....Pages 352-363
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry....Pages 364-375
Combining Binary Search Trees....Pages 376-387
The Two-Handed Tile Assembly Model Is Not Intrinsically Universal....Pages 388-399
Clustering in the Boolean Hypercube in a List Decoding Regime....Pages 400-412
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market....Pages 413-424
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds....Pages 425-436
On the Power of Deterministic Mechanisms for Facility Location Games....Pages 437-448
?2/?2-Foreach Sparse Recovery with Low Risk....Pages 449-460
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions....Pages 461-472
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets....Pages 473-484
Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete....Pages 485-496
Dynamic Compressed Strings with Random Access....Pages 497-503
The Complexity of Planar Boolean #CSP with Complex Weights....Pages 504-515
Arthur-Merlin Streaming Complexity....Pages 516-527
Local Correctability of Expander Codes....Pages 528-539
On the Complexity of Broadcast Setup....Pages 540-551
On Model-Based RIP-1 Matrices....Pages 552-563
Robust Pseudorandom Generators....Pages 564-575
A Robust AFPTAS for Online Bin Packing with Polynomial Migration,....Pages 576-588
Small Stretch Pairwise Spanners....Pages 589-600
Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions....Pages 601-612
The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization....Pages 613-624
Approximating Semi-matchings in Streaming and in Two-Party Communication....Pages 625-636
Full-Fledged Real-Time Indexing for Constant Size Alphabets....Pages 637-649
Arithmetic Circuit Lower Bounds via MaxRank....Pages 650-660
Model Checking Lower Bounds for Simple Graphs....Pages 661-672
The Complexity of Proving That a Graph Is Ramsey....Pages 673-683
An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,....Pages 684-695
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor....Pages 696-708
Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation....Pages 709-720
Graph Reconstruction via Distance Oracles....Pages 721-732
Dual Techniques for Scheduling on a Machine with Varying Speed....Pages 733-744
Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms....Pages 745-756
No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem....Pages 757-768
A Composition Theorem for the Fourier Entropy-Influence Conjecture....Pages 769-779
Large Neighborhood Local Search for the Maximum Set Packing Problem....Pages 780-791
The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom....Pages 792-803
The Complexity of Infinitely Repeated Alternating Move Games....Pages 804-815
Approximating the Diameter of Planar Graphs in Near Linear Time....Pages 816-827
Testing Linear-Invariant Function Isomorphism....Pages 828-839
Back Matter....Pages 840-850
....Pages -