Accepted Papers

The following contributions 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
• T-H. Hubert Chan and Li Ning. Fast Convergence for Consensus in Dynamic Networks
• 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
• Amin Karbasi, Stratis Ioannidis and Laurent Massoulie. Content Search Through Comparisons
• Christos Kapoutsis. Nondeterminism is Essential in Small 2FAs with Few Reversals
• 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
• Bogdan Chlebus, Dariusz Kowalski, Andrzej Pelc and Mariusz Rokicki. Efficient Distributed Communication in Ad-hoc Radio Networks
• 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
• Shiri Chechik. Fault-Tolerant Compact Routing Schemes for General Graphs
• 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
• Silvia Crafa and Francesco Ranzato. Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation
• 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
• Stefan Kiefer, Andrzej Murawski, Joel Ouaknine, James Worrell and Lijun Zhang. On Stabilization in Herman's Algorithm
• Bundit Laekhanukit. An improved approximation algorithm for the minimum-cost subset k-connectivity
• Michael Goodrich and Michael Mitzenmacher. Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
• Malte Beecken, Johannes Mittmann and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing
• Naonori Kakimura and Kazuhisa Makino. Robust Independence Systems
• Kohei Suenaga and Ichiro Hasuo. Programming with Infinitesimals: A While-Language for Hybrid System Modeling
• Tomas Brazdil, Stefan Kiefer, Antonin Kucera and Ivana Hutarova Varekova. Runtime Analysis of Probabilistic Programs with Unbounded Recursion
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Subset Feedback Vertex Set is Fixed Parameter Tractable
• Simone Bova, Hubie Chen and Matt Valeriote. Generic Expression Hardness Results for Primitive Positive Formula Comparison
• Martin Hoefer. Local Matching Dynamics in Social Networks
• Eric Allender and Fengming Wang. On the power of algebraic branching programs of width two
• Benoit Libert and Moti Yung. Adaptively Secure Non-Interactive Threshold Cryptosystems
• Shi Li. A 1.488-approximation algorithm for the uncapacitated facility location problem
• Nicole Megow, Kurt Mehlhorn and Pascal Schweitzer. Online Graph Exploration: New Results on Old and New Algorithms
• 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
• Markus Lohrey and Christian Mathissen. Isomorphism of regular trees and words
• Chien-Chung Huang. Collusion in Atomic Splittable Routing Games
• 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
• Martin Delacourt. Rice's theorem for mu-limit sets of cellular automata
• 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
• Magnús Halldórsson and Pradipta Mitra. Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model
• Carsten Moldenhauer. Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
• David Hopkins, Andrzej Murawski and Luke Ong. A Fragment of ML Decidable by Visibly Pushdown Automata
• Chandra Chekuri and Alina Ene. Submodular Cost Allocation Problem and Applications
• Kook Jin Ahn and Sudipto Guha. Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Yuval Filmus, Toniann Pitassi and Rahul Santhanam. Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
• Roberto Cominetti, Jose Correa and Omar Larre. Existence and uniqueness of equilibria  for flows over time
• 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
• Olivier Carton, Thomas Colcombet and Gabriele Puppis. Regular Languages of Words Over Countable Linear Orderings
• Vince Barany, Balder Ten Cate and Luc Segoufin. Guarded negation
• 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?
• Matthew Anderson, Dieter Van Melkebeek, Nicole Schweikardt and Luc Segoufin. Locality of queries definable in invariant first-order logic  with arbitrary built-in predicates
• Daniel Reichman and Uriel Feige. Recoverable Values for Independent Sets
• Danny Hermelin, Avivit Levy, Oren Weimann and Raphael Yuster. Distance Oracles for Vertex-Labeled Graphs
• 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
• Shin-Ya Katsumata. Relating Computational Effects by TT-Lifting
• Jim Laird, Giulio Manzonetto and Guy Mccusker. Constructing differential categories and deconstructing categories of games
• Radu Mardare, Luca Cardelli and Kim Larsen. Modular Markovian Logic
• 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
• Georg Zetzsche. On the capabilities of grammars, automata, and transducers controlled by monoids
• Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Amélie Stainer. Emptiness and Universality Problems in Timed Automata with Positive Frequency
• 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
• Holger Hermanns, David N. Jansen, Flemming Nielson and Lijun Zhang. Automata-based CSL model checking
• Stefan Canzar, Khaled Elbassioni, Gunnar W. Klau and Julián Mestre. On Tree-Constrained Matchings and Generalizations
• Johannes Dams, Martin Hoefer and Thomas Kesselheim. Convergence Time of Power Control Dynamics
• Michael Benedikt, Gabriele Puppis and Cristian Riveros. The cost of traveling between languages
• Alexey Gotsman and Hongseok Yang. Liveness-preserving atomicity abstraction
• 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
• Thomas Brihaye, Laurent Doyen, Gilles Geeraerts, Joël Ouaknine, Jean-François Raskin and James Worrell. On Reachability for Hybrid Automata over Bounded Time
• 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
• Sylvain Schmitz and Philippe Schnoebelen. Multiply-Recursive Upper Bounds with Higman’s Lemma
• 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
• Lorenzo Clemente. Buechi Automata can have Smaller Quotients
• Matthew Hennessy and Yuxin Deng. On the Semantics of Markov Automata
• 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
• Sylvain Salvati and Igor Walukiewicz. Krivine machines and higher-order schemes
• Benjamin Doerr and Mahmoud Fouz. Asymptotically Optimal Randomized Rumor Spreading
• Eric Allender, Luke Friedman and William Gasarch. Limits on the Computational Power of Random Strings
• Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes, Friedhelm Meyer Auf Der Heide, Sven Kurras, Matthias Fischer, Martina Hüllmann, Alexander Klaas, Peter Kling, Marcus Märtens, Kamil Swierkot, Christoph Raupach, Daniel Warner, Christoph Weddemann and Daniel Wonisch. A new Approach for Analyzing Convergence Algorithms for Mobile Robots
• Ahmed Bouajjani, Roland Meyer and Eike Moehlmann. Deciding robustness against total store ordering
• Konstantinos Kollias and Tim Roughgarden. Restoring Pure Equilibria to Weighted Congestion Games
• Diana Fischer and Lukasz Kaiser. Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems
• Konstantinos Tsakalidis and Gerth Stølting Brodal. Dynamic Planar Range Maxima Queries
• Tomas Brazdil, Vaclav Brozek, Kousha Etessami and Antonin Kucera. Approximating the Termination Value of One-counter MDPs and Stochastic Games
• 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
• Franck Van Breugel and Xin Zhang. A Progress Measure for Explicit-State Probabilistic Model-Checkers