Personal tools
You are here: Home Track A Accepted Papers (Track A)

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.

  • 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
Document Actions