List of Accepted Papers

The following is a preliminary list of the papers accepted to FOCS 2009.

• 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.