# Accepted Papers (Track A)

by
Michael Hoffmann
—
last modified
Apr 13, 2011 10:01 AM

The following contributions to Track A have been accepted for presentation at ICALP 2011. They are listed in no particular order.

**There is also a list including abstracts.**

- A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
- On variants of file caching
- Constraint satisfaction parameterized by solution size
- Vertex Cover in Graphs with Locally Few Colors
- Efficient Sample Extractors for Juntas with Applications
- Center stable matchings and centers of cover graphs of distributive lattices
- Limitations on quantum dimensionality reduction
- On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
- On the power of lower bound methods for one-way quantum communication complexity
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Popular Matchings in the Stable Marriage Problem
- An O(log n)-competitive algorithm for online constrained forest problems
- Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
- Clustering with Local Restrictions
- The decimation process in random k-SAT
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- An improved approximation algorithm for the minimum-cost subset k-connectivity
- Algebraic Independence and Blackbox Identity Testing
- Robust Independence Systems
- Subset Feedback Vertex Set is Fixed Parameter Tractable
- On the power of algebraic branching programs of width two
- A 1.488-approximation algorithm for the uncapacitated facility location problem
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
- Pairwise-interaction Games
- Clique Clustering yields a PTAS for max-Coloring Interval Graphs
- Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
- A Tighter Insertion-based Approximation of the Crossing Number
- On the Advice Complexity of the k-Server Problem
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
- Submodular Cost Allocation Problem and Applications
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
- Player-Centric Byzantine Agreement
- Maximizing a Polynomial Subject to Assignment Constraints
- Domination when the Stars Are Out
- VC-Dimension and Shortest Path Algorithms
- Tight Bounds for Linkages in Planar Graphs
- The Complexity of Symmetric Boolean Parity Holant Problems
- New Algorithms for Learning in Presence of Errors
- Compact Navigation and Distance Oracles for Graphs with Small Treewidth
- Buyback Problem - Approximate matroid intersection with cancellation costs
- Meeting deadlines: How much speed suffices?
- Recoverable Values for Independent Sets
- Linear Programming and Combinatorial Bounds on Steiner Transitive-Closure Spanners
- Sorting by Transpositions is Difficult
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Settling the complexity of local max-cut (almost) completely
- Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
- Automatizability and Simple Stochastic Games
- On Tree-Constrained Matchings and Generalizations
- Parameterized Bounded-Depth Frege is Not Optimal
- Range Majority in Constant Time and Linear Space
- Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
- Advice Coins for Classical and Quantum Computation
- Sleep Management on Multiple Machines for Energy and Flow Time
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
- Robust Simulations and Significant Separations
- The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
- Improved bounds for the randomized decision tree complexity of recursive majority
- Quantum Commitments from Complexity Assumptions
- Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience
- Limits on the Computational Power of Random Strings
- Dynamic Planar Range Maxima Queries
- Approximation schemes for capacitated geometric network design
- Improved Approximation for the Directed Spanner Problem
- Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
- A PCP Characterization of AM