The two-volume set LNCS 6755 and LNCS 6756 constitutes the refereed proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, held in Zürich, Switzerland, in July 2011. The 114 revised full papers (68 papers for track A, 29 for track B, and 17 for track C) presented together with 4 invited talks, 3 best student papers, and 3 best papers were carefully reviewed and selected from a total of 398 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management.
Author(s): Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova (auth.), Luca Aceto, Monika Henzinger, Jiří Sgall (eds.)
Series: Lecture Notes in Computer Science 6755
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 802
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Computer Communication Networks; Information Storage and Retrieval; Discrete Mathematics in Computer Science
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 -
