Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I

Front Matter....Pages -
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method....Pages 1-12
The NOF Multiparty Communication Complexity of Composed Functions....Pages 13-24
Quantum Strategies Are Better Than Classical in Almost Any XOR Game....Pages 25-37
Efficient Submodular Function Maximization under Linear Packing Constraints....Pages 38-50
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups....Pages 51-62
Clustering under Perturbation Resilience....Pages 63-74
Secretary Problems with Convex Costs....Pages 75-87
Nearly Simultaneously Resettable Black-Box Zero Knowledge....Pages 88-99
Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity....Pages 100-108
On Quadratic Programming with a Ratio Objective....Pages 109-120
De-amortizing Binary Search Trees....Pages 121-132
Efficient Sampling Methods for Discrete Distributions....Pages 133-144
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints....Pages 145-156
Improved LP-Rounding Approximation Algorithm for k -level Uncapacitated Facility Location....Pages 157-169
Testing Coverage Functions....Pages 170-181
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree....Pages 182-193
A Dependent LP-Rounding Approach for the k -Median Problem....Pages 194-205
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs....Pages 206-217
Computing the Visibility Polygon of an Island in a Polygonal Domain....Pages 218-229
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable....Pages 230-241
Max-Cut Parameterized above the Edwards-Erdős Bound....Pages 242-253
Clique Cover and Graph Separation: New Incompressibility Results....Pages 254-265
The Inverse Shapley Value Problem....Pages 266-277
Zero-One Rounding of Singular Vectors....Pages 278-289
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner....Pages 290-301
Space-Constrained Interval Selection....Pages 302-313
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations....Pages 314-326
Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima....Pages 327-338
Universal Factor Graphs....Pages 339-350
Parameterized Approximation via Fidelity Preserving Transformations....Pages 351-362
Backdoors to Acyclic SAT....Pages 363-374
Dominators, Directed Bipolar Orders, and Independent Spanning Trees....Pages 375-386
Hardness of Approximation for Quantum Problems....Pages 387-398
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)....Pages 399-410
Stochastic Vehicle Routing with Recourse....Pages 411-423
The Online Metric Matching Problem for Doubling Metrics....Pages 424-435
Approximating Sparse Covering Integer Programs Online....Pages 436-448
Streaming and Communication Complexity of Clique Approximation....Pages 449-460
Distributed Private Heavy Hitters....Pages 461-472
A Thirty Year Old Conjecture about Promise Problems....Pages 473-484
Minimum Latency Submodular Cover....Pages 485-497
Constant-Time Algorithms for Sparsity Matroids....Pages 498-509
CRAM: Compressed Random Access Memory....Pages 510-521
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision....Pages 522-532
Faster Fully Compressed Pattern Matching by Recompression....Pages 533-544
NNS Lower Bounds via Metric Expansion for l  ∞  and EMD ....Pages 545-556
Quantum Adversary (Upper) Bound....Pages 557-568
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time....Pages 569-580
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs....Pages 581-593
Preserving Terminal Distances Using Minors....Pages 594-605
A Rounding by Sampling Approach to the Minimum Size k -Arc Connected Subgraph Problem....Pages 606-616
Classical and Quantum Partition Bound and Detector Inefficiency....Pages 617-628
Testing Similar Means....Pages 629-640
The Parameterized Complexity of k -Edge Induced Subgraphs....Pages 641-652
Converting Online Algorithms to Local Computation Algorithms....Pages 653-664
Assigning Sporadic Tasks to Unrelated Parallel Machines....Pages 665-676
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals....Pages 677-688
The Power of Recourse for Online MST and TSP....Pages 689-700
Geometry of Online Packing Linear Programs....Pages 701-713
Self-assembly with Geometric Tiles....Pages 714-725
Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation....Pages 726-737
Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions....Pages 738-749
Parameterized Tractability of Multiway Cut with Parity Constraints....Pages 750-761
Set Cover Revisited: Hypergraph Cover with Hard Capacities....Pages 762-773
On the Limits of Sparsification....Pages 774-785
Certifying 3-Connectivity in Linear Time....Pages 786-797
Epsilon-Net Method for Optimizations over Separable States....Pages 798-809
Faster Algorithms for Privately Releasing Marginals....Pages 810-821
Stochastic Matching with Commitment....Pages 822-833
 Rademacher-Sketch : A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance....Pages 834-845
A Matrix Hyperbolic Cosine Algorithm and Applications....Pages 846-858
Back Matter....Pages -