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

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
Counting Matchings of Size k Is $\sharp$ W [1]-Hard....Pages 352-363
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree....Pages 364-375
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry....Pages 376-387
Combining Binary Search Trees....Pages 388-399
The Two-Handed Tile Assembly Model Is Not Intrinsically Universal....Pages 400-412
Clustering in the Boolean Hypercube in a List Decoding Regime....Pages 413-424
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market....Pages 425-436
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds....Pages 437-448
On the Power of Deterministic Mechanisms for Facility Location Games....Pages 449-460
ℓ 2 /ℓ 2 -Foreach Sparse Recovery with Low Risk....Pages 461-472
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions....Pages 473-484
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets....Pages 485-496
Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete....Pages 497-503
Dynamic Compressed Strings with Random Access....Pages 504-515
The Complexity of Planar Boolean #CSP with Complex Weights....Pages 516-527
Arthur-Merlin Streaming Complexity....Pages 528-539
Local Correctability of Expander Codes....Pages 540-551
On the Complexity of Broadcast Setup....Pages 552-563
On Model-Based RIP-1 Matrices....Pages 564-575
Robust Pseudorandom Generators....Pages 576-588
A Robust AFPTAS for Online Bin Packing with Polynomial Migration,....Pages 589-600
Small Stretch Pairwise Spanners....Pages 601-612
Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions....Pages 613-624
The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization....Pages 625-636
Approximating Semi-matchings in Streaming and in Two-Party Communication....Pages 637-649
Full-Fledged Real-Time Indexing for Constant Size Alphabets....Pages 650-660
Arithmetic Circuit Lower Bounds via MaxRank....Pages 661-672
Model Checking Lower Bounds for Simple Graphs....Pages 673-683
The Complexity of Proving That a Graph Is Ramsey....Pages 684-695
An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,....Pages 696-708
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor....Pages 709-720
Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation....Pages 721-732
Graph Reconstruction via Distance Oracles....Pages 733-744
Dual Techniques for Scheduling on a Machine with Varying Speed....Pages 745-756
Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms....Pages 757-768
No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem....Pages 769-779
A Composition Theorem for the Fourier Entropy-Influence Conjecture....Pages 780-791
Large Neighborhood Local Search for the Maximum Set Packing Problem....Pages 792-803
The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom....Pages 804-815
The Complexity of Infinitely Repeated Alternating Move Games....Pages 816-827
Approximating the Diameter of Planar Graphs in Near Linear Time....Pages 828-839
Testing Linear-Invariant Function Isomorphism....Pages 840-850
Back Matter....Pages -