Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I

Front Matter....Pages -
Improved Approximation for the Directed Spanner Problem....Pages 1-12
An Improved Approximation Algorithm for Minimum-Cost Subset k -Connectivity....Pages 13-24
Approximation Schemes for Capacitated Geometric Network Design....Pages 25-36
An O (log n )-Competitive Algorithm for Online Constrained Forest Problems....Pages 37-48
On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity....Pages 49-60
Advice Coins for Classical and Quantum Computation....Pages 61-72
Quantum Commitments from Complexity Assumptions....Pages 73-85
Limitations on Quantum Dimensionality Reduction....Pages 86-97
On Tree-Constrained Matchings and Generalizations....Pages 98-109
Tight Bounds for Linkages in Planar Graphs....Pages 110-121
A Tighter Insertion-Based Approximation of the Crossing Number....Pages 122-134
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs....Pages 135-146
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes....Pages 147-158
Pairwise-Interaction Games....Pages 159-170
Settling the Complexity of Local Max-Cut (Almost) Completely....Pages 171-182
Clique Clustering Yields a PTAS for max-Coloring Interval Graphs....Pages 183-194
On Variants of File Caching....Pages 195-206
On the Advice Complexity of the k-Server Problem....Pages 207-218
Sleep Management on Multiple Machines for Energy and Flow Time....Pages 219-231
Meeting Deadlines: How Much Speed Suffices?....Pages 232-243
Range Majority in Constant Time and Linear Space....Pages 244-255
Dynamic Planar Range Maxima Queries....Pages 256-267
Compact Navigation and Distance Oracles for Graphs with Small Treewidth....Pages 268-280
Player-Centric Byzantine Agreement....Pages 281-292
Limits on the Computational Power of Random Strings....Pages 293-304
The Decimation Process in Random k -SAT....Pages 305-316
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority....Pages 317-329
The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions....Pages 330-341
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm....Pages 342-353
Submodular Cost Allocation Problem and Applications....Pages 354-366
Robust Independence Systems....Pages 367-378
Buyback Problem - Approximate Matroid Intersection with Cancellation Costs....Pages 379-390
Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience....Pages 391-402
New Algorithms for Learning in Presence of Errors....Pages 403-415
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds....Pages 416-423
Constraint Satisfaction Parameterized by Solution Size....Pages 424-436
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization....Pages 437-448
Subset Feedback Vertex Set Is Fixed-Parameter Tractable....Pages 449-461
Domination When the Stars Are Out....Pages 462-473
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem....Pages 474-485
Recoverable Values for Independent Sets....Pages 486-497
Vertex Cover in Graphs with Locally Few Colors....Pages 498-509
Maximizing Polynomials Subject to Assignment Constraints....Pages 510-520
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid....Pages 521-532
Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width....Pages 533-544
Efficient Sample Extractors for Juntas with Applications....Pages 545-556
Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications....Pages 557-568
Robust Simulations and Significant Separations....Pages 569-580
A PCP Characterization of AM....Pages 581-592
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model....Pages 593-604
Automatizability and Simple Stochastic Games....Pages 605-617
Exponential Lower Bounds for AC 0 -Frege Imply Superpolynomial Frege Lower Bounds....Pages 618-629
Parameterized Bounded-Depth Frege Is Not Optimal....Pages 630-641
On Minimal Unsatisfiability and Time-Space Trade-offs for k -DNF Resolution....Pages 642-653
Sorting by Transpositions Is Difficult....Pages 654-665
Popular Matchings in the Stable Marriage Problem....Pages 666-677
Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices....Pages 678-689
VC-Dimension and Shortest Path Algorithms....Pages 690-699
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems....Pages 700-711
The Complexity of Symmetric Boolean Parity Holant Problems....Pages 712-723
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth....Pages 724-735
On the Power of Algebraic Branching Programs of Width Two....Pages 736-747
Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs....Pages 748-759
Steiner Transitive-Closure Spanners of Low-Dimensional Posets....Pages 760-772
Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere....Pages 773-784
Clustering with Local Restrictions....Pages 785-797
Back Matter....Pages -