FOCS 2009 Main Page



Accepted Papers


List of Accepted Papers

The following is a preliminary list of the papers accepted to FOCS 2009.  A list of the papers with abstracts may be found here.

  • Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions
    Zeev Nutov.
  • Randomized Self-Assembly for Exact Shapes
    David Doty.
  • Symmetry and approximability of submodular maximization problems
    Jan Vondrak.
  • Fully Dynamic $(2 + \eps)$ Approximate All-Pairs Shortest Paths with $O(\log \log n)$ Query and Close to Linear Update Time
    Aaron Bernstein.
  • Bounded Independence Fools Halfspaces
    Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola.
  • A Parallel Repetition Theorem for Any Interactive Argument
    Iftach Haitner.
  • Two-message quantum interactive proofs are in PSPACE
    Rahul Jain, Sarvagya Upadhyay and John Watrous.
  • Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers
    Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan.
  • Optimal Long Code Test with One Free Bit
    Nikhil Bansal and Subhash Khot.
  • Combinatorial PCPs with efficient verifiers
    Or Meir.
  • A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP
    Jeff Cheeger, Bruce Kleiner and Assaf Naor.
  • Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
    Ben Reichardt.
  • Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
    Dang-Trinh Huynh-Ngoc and Paul Beame.
  • Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
    Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Howard Karloff.
  • Delaunay Triangulations in O(sort(n)) and Other Transdichotomous and Hereditary Algorithms in Computational Geometry
    Kevin Buchin and Wolfgang Mulzer.
  • Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
    Saugata Basu and Thierry Zell.
  • Learning and Smoothed Analysis
    Adam Kalai, Alex Samorodnitsky and Shang-Hua Teng.
  • A Complete Characterization of Statistical Query Learning with Applications to Evolvability
    Vitaly Feldman.
  • Optimal quantum strong coin flipping
    André Chailloux and Iordanis Kerenidis.
  • Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
    Ankur Moitra.
  • Submodular Function Minimization under Covering Constraints
    Satoru Iwata and Kiyohito Nagano.
  • An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
    Julia Chuzhoy and Sanjeev Khanna.
  • Blackbox Polynomial Identity Testing for Depth 3 Circuits
    Neeraj Kayal and Shubhangi Saraf.
  • The Complexity of Rationalizing Network Formation
    Shankar Kalyanaraman and Christopher Umans.
  • Exact And Approximate Pattern Matching In The Streaming Model
    Ely Porat and Benny Porat.
  • A new probability inequality using typical moments and concentration results
    Ravindran Kannan.
  • Orthogonal Range Reporting in Three and Higher Dimensions
    Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen.
  • Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
    Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.
  • SDP Integrality Gaps with Local $\ell_1$-Embeddability
    Subhash Khot and Rishi Saket.
  • On the Power of Randomization in Algorithmic Mechanism Design
    Shahar Dobzinski and Shaddin Dughmi.
  • Constraint Satisfaction Problems of Bounded Width
    Libor Barto and Marcin Kozik.
  • On Allocating Goods to Maximize Fairness
    Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
  • Regularity Lemmas and Combinatorial Algorithms
    Nikhil Bansal and Ryan Williams.
  • One bit encryption is complete
    Steven Myers and abhi shelat.
  • Composition of low-error 2-query PCPs using decodable PCPs
    Irit Dinur and Prahladh Harsha.
  • Smoothed Analysis of Multiobjective Optimization
    Heiko Roeglin and Shang-Hua Teng.
  • k-Means has Polynomial Smoothed Complexity
    David Arthur, Bodo Manthey and Heiko Roeglin.
  • Reducibility Among Fractional Stability Problems
    Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.
  • Online Stochastic Matching: Beating 1-1/e
    Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.
  • The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
    Sandy Irani and Daniel Gottesman.
  • Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
    Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng.
  • Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
    Yi Deng, Vipul Goyal and Amit Sahai.
  • Space-Efficient Framework for Top-k String Retrieval Problems
    Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter.
  • (Meta) Kernelization
    Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos.
  • Choice-memory tradeoff in allocations
    Noga Alon, Ori Gurel-Gurevich and Eyal Lubetzky.
  • The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
    Eyal Kushilevitz and Enav Weinreb.
  • Convergence to Equilibrium in Local Interaction Games
    Andrea Montanari and Amin Saberi.
  • Instance-Optimal Geometric Algorithms
    Peyman Afshani, Jeremy Barbay and Timothy M. Chan.
  • Planarity allowing few error vertices in linear time
    Ken-ichi Kawarabayashi.
  • Constructing Small-Bias Sets from Algebraic-Geometric Codes
    Avraham Ben-Aroya and Amnon Ta-Shma.
  • Oblivious Routing for the L_p-norm
    Matthias Englert and Harald Räcke.
  • The Intersection of Two Halfspaces Has High Threshold Degree
    Alexander Sherstov.
  • Distance Oracles for Sparse Graphs
    Christian Sommer, Elad Verbin and Wei Yu.
  • Universal Blind Quantum Computation
    Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.
  • Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization
    Tanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.
  • Decomposing Coverings and the Planar Sensor Cover Problem
    Matt Gibson and Kasturi Varadarajan.
  • Extracting Correlations
    Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.
  • The Data Stream Space Complexity of Cascaded Norms
    T.S. Jayram and David Woodruff.
  • Faster generation of random spanning trees
    Jonathan Kelner and Aleksander Madry.
  • Integrality gaps for Strong SDP Relaxations of Unique Games
    Prasad Raghavendra and David Steurer.
  • How to Round Any CSP
    Prasad Raghavendra and David Steurer.
  • KKL, Kruskal-Katona, and monotone nets
    Ryan O'Donnell and Karl Wimmer.
  • Higher eigenvalues of graphs
    Jonathan Kelner, James Lee, Gregory Price and Shanghua Teng.
  • Efficient sketches for Earth-Mover Distance, with applications
    Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.
  • Agnostic Learning of Monomials by Halfspaces is Hard
    Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.
  • An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
    Ashish Goel and Ian Post.
  • Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
    Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.
  • Local Graph Partitions for Approximation and Testing
    Avinatan Hassidim, Jonathan Kelner, Huy Nguyen and Krzysztof Onak.
  • Linear systems over composite moduli
    Arkadev Chattopadhyay and Avi Wigderson.
  • Models for the compressible Web
    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi and Prabhakar Raghavan.
  • Breaking the Multicommodity Flow Barrier for O(sqrt(log n))-approximations to Sparsest Cut
    Jonah Sherman.
  • A Probabilistic Inequality with Applications to Threshold Direct Product Theorems
    Falk Unger.
  • 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness
    Yael Tauman Kalai, Xin Li and Anup Rao.