List of accepted papers for ICALP 2011: Track A: 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 Daniel Marx. Constraint satisfaction parameterized by solution size Fabian Kuhn and Monaldo Mastrolilli. Vertex Cover in Graphs with Locally Few Colors Sourav Chakraborty, David Garcia-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 Daniel 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 Julian 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 Andre 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 Stolting 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 Track B: Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Amelie Stainer. Emptiness and Universality Problems in Timed Automata with Positive Frequency Georg Zetzsche. On the capabilities of grammars, automata, and transducers controlled by monoids Tomas Brazdil, Vaclav Brozek, Kousha Etessami and Antonin Kucera. Approximating the Termination Value of One-counter MDPs and Stochastic Games Thomas Brihaye, Laurent Doyen, Gilles Geeraerts, Joel Ouaknine, Jean-Francois Raskin and James Worrell. On Reachability for Hybrid Automata over Bounded Time Kohei Suenaga and Ichiro Hasuo. Programming with Infinitesimals: A While-Language for Hybrid System Modeling Franck Van Breugel and Xin Zhang. A Progress Measure for Explicit-State Probabilistic Model-Checkers Christos Kapoutsis. Nondeterminism is Essential in Small 2FAs with Few Reversals Lorenzo Clemente. Buechi Automata can have Smaller Quotients Vince Barany, Balder Ten Cate and Luc Segoufin. Guarded negation Radu Mardare, Luca Cardelli and Kim Larsen. Modular Markovian Logic Simone Bova, Hubie Chen and Matt Valeriote. Generic Expression Hardness Results for Primitive Positive Formula Comparison Sylvain Salvati and Igor Walukiewicz. Krivine machines and higher-order schemes Martin Delacourt. Rice's theorem for mu-limit sets of cellular automata Michael Benedikt, Gabriele Puppis and Cristian Riveros. The cost of traveling between languages Matthew Anderson, Dieter Van Melkebeek, Nicole Schweikardt and Luc Segoufin. Locality of queries definable in invariant first-order logic with arbitrary built-in predicates Markus Lohrey and Christian Mathissen. Isomorphism of regular trees and words Ahmed Bouajjani, Roland Meyer and Eike Moehlmann. Deciding robustness against total store ordering Olivier Carton, Thomas Colcombet and Gabriele Puppis. Regular Languages of Words Over Countable Linear Orderings Matthew Hennessy and Yuxin Deng. On the Semantics of Markov Automata Alexey Gotsman and Hongseok Yang. Liveness-preserving atomicity abstraction Holger Hermanns, David N. Jansen, Flemming Nielson and Lijun Zhang. Automata-based CSL model checking Sylvain Schmitz and Philippe Schnoebelen. Multiply-Recursive Upper Bounds with Higman’s Lemma Diana Fischer and Lukasz Kaiser. Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems Tomas Brazdil, Stefan Kiefer, Antonin Kucera and Ivana Hutarova Varekova. Runtime Analysis of Probabilistic Programs with Unbounded Recursion Shin-Ya Katsumata. Relating Computational Effects by TT-Lifting Jim Laird, Giulio Manzonetto and Guy Mccusker. Constructing differential categories and deconstructing categories of games Silvia Crafa and Francesco Ranzato. Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation David Hopkins, Andrzej Murawski and Luke Ong. A Fragment of ML Decidable by Visibly Pushdown Automata Stefan Kiefer, Andrzej Murawski, Joel Ouaknine, James Worrell and Lijun Zhang. On Stabilization in Herman's Algorithm Track C: Martin Hoefer. Local Matching Dynamics in Social Networks Kook Jin Ahn and Sudipto Guha. Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem T-H. Hubert Chan and Li Ning. Fast Convergence for Consensus in Dynamic Networks Shiri Chechik. Fault-Tolerant Compact Routing Schemes for General Graphs Amin Karbasi, Stratis Ioannidis and Laurent Massoulie. Content Search Through Comparisons Bogdan Chlebus, Dariusz Kowalski, Andrzej Pelc and Mariusz Rokicki. Efficient Distributed Communication in Ad-hoc Radio Networks Nicole Megow, Kurt Mehlhorn and Pascal Schweitzer. Online Graph Exploration: New Results on Old and New Algorithms Michael Goodrich and Michael Mitzenmacher. Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation Chien-Chung Huang. Collusion in Atomic Splittable Routing Games Magnus Halldorsson and Pradipta Mitra. Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model Benjamin Doerr and Mahmoud Fouz. Asymptotically Optimal Randomized Rumor Spreading Danny Hermelin, Avivit Levy, Oren Weimann and Raphael Yuster. Distance Oracles for Vertex-Labeled Graphs Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes, Friedhelm Meyer Auf Der Heide, Sven Kurras, Matthias Fischer, Martina Hullmann, Alexander Klaas, Peter Kling, Marcus Martens, Kamil Swierkot, Christoph Raupach, Daniel Warner, Christoph Weddemann and Daniel Wonisch. A new Approach for Analyzing Convergence Algorithms for Mobile Robots Johannes Dams, Martin Hoefer and Thomas Kesselheim. Convergence Time of Power Control Dynamics Konstantinos Kollias and Tim Roughgarden. Restoring Pure Equilibria to Weighted Congestion Games Benoit Libert and Moti Yung. Adaptively Secure Non-Interactive Threshold Cryptosystems Roberto Cominetti, Jose Correa and Omar Larre. Existence and uniqueness of equilibria for flows over time