Track A: Accepted Papers

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 corresponding list including abstracts.

• Leslie Ann Goldberg and Mark Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
• Leah Epstein, Csanad Imreh, Asaf Levin and Judit Nagy-Gyorgy. On variants of file caching
• Andrei Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size
• Fabian Kuhn and Monaldo Mastrolilli. Vertex Cover in Graphs with Locally Few Colors
• Sourav Chakraborty, David García-Soriano and Arie Matsliah. Efficient Sample Extractors for Juntas with Applications
• Christine Cheng, Eric Mcdermid and Ichiro Suzuki. Center stable matchings and centers of cover graphs of distributive lattices
• Ashley Montanaro, Aram Harrow and Anthony Short. Limitations on quantum dimensionality reduction
• Jakob Nordstrom and Alexander Razborov. On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
• Shengyu Zhang. On the power of lower bound methods for one-way quantum communication complexity
• Markus Jalsenius and Raphael Clifford. Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• Chien-Chung Huang and Telikepalli Kavitha. Popular Matchings in the Stable Marriage Problem
• Jiawei Qian and David Williamson. An O(log n)-competitive algorithm for online constrained forest problems
• Hung Ngo, Ely Porat and Atri Rudra. Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
• Daniel Lokshtanov and Dániel Marx. Clustering with Local Restrictions
• Amin Coja-Oghlan and Angelica Pachon-Pinzon. The decimation process in random k-SAT
• Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Bundit Laekhanukit. An improved approximation algorithm for the minimum-cost subset k-connectivity
• Malte Beecken, Johannes Mittmann and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing
• Naonori Kakimura and Kazuhisa Makino. Robust Independence Systems
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Subset Feedback Vertex Set is Fixed Parameter Tractable
• Eric Allender and Fengming Wang. On the power of algebraic branching programs of width two
• Shi Li. A 1.488-approximation algorithm for the uncapacitated facility location problem
• Ken-Ichi Kawarabayashi, Philip Klein and Christian Sommer. Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
• Velumailum Mohanaraj and Martin Dyer. Pairwise-interaction Games
• Tim Nonner. Clique Clustering yields a PTAS for max-Coloring Interval Graphs
• Hu Ding and Jinhui Xu. Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
• Markus Chimani and Petr Hlineny. A Tighter Insertion-based Approximation of the Crossing Number
• Hans-Joachim Boeckenhauer, Dennis Komm, Rastislav Kralovic and Richard Kralovic. On the Advice Complexity of the k-Server Problem
• Stefan Mengel. Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Carsten Moldenhauer. Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
• Chandra Chekuri and Alina Ene. Submodular Cost Allocation Problem and Applications
• Yuval Filmus, Toniann Pitassi and Rahul Santhanam. Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
• Maurice Jansen and Rahul Santhanam. Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
• Vassilis Zikas and Martin Hirt. Player-Centric Byzantine Agreement
• Konstantin Makarychev and Maxim Sviridenko. Maximizing a Polynomial Subject to Assignment Constraints
• Danny Hermelin, Matthias Mnich, Erik Jan Van Leeuwen and Gerhard J. Woeginger. Domination when the Stars Are Out
• Ittai Abraham, Daniel Delling, Amos Fiat, Andrew Goldberg and Renato Werneck. VC-Dimension and Shortest Path Algorithms
• Isolde Adler, Stavros Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos. Tight Bounds for Linkages in Planar Graphs
• Heng Guo, Pinyan Lu and Leslie Valiant. The Complexity of Symmetric Boolean Parity Holant Problems
• Sanjeev Arora and Rong Ge. New Algorithms for Learning in Presence of Errors
• Arash Farzan and Shahin Kamali. Compact Navigation and Distance Oracles for Graphs with Small Treewidth
• Ashwinkumar Badanidiyuru Varadaraja. Buyback Problem - Approximate matroid intersection with  cancellation costs
• Anand S, Naveen Garg and Nicole Megow. Meeting deadlines: How much speed suffices?
• Daniel Reichman and Uriel Feige. Recoverable Values for Independent Sets
• Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff and Grigory Yaroslavtsev. Linear Programming and Combinatorial Bounds on Steiner Transitive-Closure Spanners
• Laurent Bulteau, Guillaume Fertin and Irena Rusu. Sorting by Transpositions is Difficult
• Moran Feldman, Seffi Naor and Roy Schwartz. Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
• Robert Elsaesser and Tobias Tscheuschner. Settling the complexity of local max-cut (almost) completely
• Magnus Bordewich and Ross J. Kang. Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Lei Huang and Toniann Pitassi. Automatizability and Simple Stochastic Games
• Stefan Canzar, Khaled Elbassioni, Gunnar W. Klau and Julián Mestre. On Tree-Constrained Matchings and Generalizations
• Olaf Beyersdorff, Nicola Galesi, Massimo Lauria and Alexander Razborov. Parameterized Bounded-Depth Frege is Not Optimal
• Stephane Durocher, Meng He, Ian Munro, Patrick Nicholson and Matthew Skala. Range Majority in Constant Time and Linear Space
• Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino and Bodo Manthey. Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
• Scott Aaronson and Andrew Drucker. Advice Coins for Classical and Quantum Computation
• Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Chi-Man Liu and Hing-Fung Ting. Sleep Management on Multiple Machines for Energy and Flow Time
• Subhash Khot and Per Austrin. A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Lance Fortnow and Rahul Santhanam. Robust Simulations and Significant Separations
• Ryan O'Donnell, John Wright and Yuan Zhou. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
• Frederic Magniez, Ashwin Nayak, Miklos Santha and David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority
• André Chailloux, Iordanis Kerenidis and Bill Rosgen. Quantum Commitments from Complexity Assumptions
• Sebastian Faust, Krzysztof Pietrzak and Daniele Venturi. Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience
• Eric Allender, Luke Friedman and William Gasarch. Limits on the Computational Power of Random Strings
• Konstantinos Tsakalidis and Gerth Stølting Brodal. Dynamic Planar Range Maxima Queries
• Anna Adamaszek, Artur Czumaj, Andrzej Lingas and Jakub Onufry Wojtaszczyk. Approximation schemes for capacitated geometric network design
• Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev. Improved Approximation for the Directed Spanner Problem
• Ryan Harkins and John Hitchcock. Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
• Andrew Drucker. A PCP Characterization of AM