FOCS 2009 Accepted Papers (with pdf files)

FOCS 2009 accepted paper list is here. List with abstracts is here. Following is a list with links to pdf files. Leave a comment if I missed any pdf files. If you haven't uploaded your accepted paper on your homepages please do so.

• Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions [pdf]
  Zeev Nutov.

• Randomized Self-Assembly for Exact Shapes [pdf]
  David Doty.

• Symmetry and approximability of submodular maximization problems [pdf]
  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 [pdf]
  Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola.

• A Parallel Repetition Theorem for Any Interactive Argument [pdf]
  Iftach Haitner.

• Two-message quantum interactive proofs are in PSPACE [arXiv]
  Rahul Jain, Sarvagya Upadhyay and John Watrous.

• Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers [pdf]
  Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan.

• Optimal Long Code Test with One Free Bit [ps]
  Nikhil Bansal and Subhash Khot.

• Combinatorial PCPs with efficient verifiers [pdf] [summary]
  Or Meir.

• A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP [arXiv]
  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. [arXiv]
  

• Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
  Dang-Trinh Huynh-Ngoc and Paul Beame. [pdf]
  

• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP [pdf]
  Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Howard Karloff.

• Delaunay Triangulations in O(sort(n)) and Other Transdichotomous and Hereditary Algorithms in Computational Geometry [pdf] [summary]
  Kevin Buchin and Wolfgang Mulzer.

• Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
  Saugata Basu and Thierry Zell. [arXiv]

• Learning Decision Trees From Random Examples: a Smoothed Analysis [pdf]
  Adam Kalai, Shang-Hua Teng and Alex Samorodnitsky.

• A Complete Characterization of Statistical Query Learning with Applications to Evolvability [pdf]
  Vitaly Feldman.

• Optimal quantum strong coin flipping [arXiv]
  André Chailloux and Iordanis Kerenidis.

• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size [pdf]
  Ankur Moitra.

• Submodular Function Minimization under Covering Constraints [ps.gz]
  Satoru Iwata and Kiyohito Nagano.

• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design [arXiv]
  Julia Chuzhoy and Sanjeev Khanna.

• Blackbox Polynomial Identity Testing for Depth 3 Circuits [ECCC]
  Neeraj Kayal and Shubhangi Saraf.

• The Complexity of Rationalizing Network Formation [pdf]
  Shankar Kalyanaraman and Christopher Umans.

• Exact And Approximate Pattern Matching In The Streaming Model
  Ely Porat and Benny Porat.

• A new probability using typical moments and concentration results [arXiv]
  Ravindran Kannan.

• Orthogonal Range Reporting in Three and Higher Dimensions [pdf]
  Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen.

• Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks [arXiv]
  Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.

• SDP Integrality Gaps with Local $\ell_1$-Embeddability [pdf]
  Subhash Khot and Rishi Saket.

• On the Power of Randomization in Algorithmic Mechanism Design [pdf]
  Shahar Dobzinski and Shaddin Dughmi.

• Constraint Satisfaction Problems of Bounded Width [pdf] [slides]
  Libor Barto and Marcin Kozik.

• On Allocating Goods to Maximize Fairness [arXiv]
  Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
  

• Regularity Lemmas and Combinatorial Algorithms [summary] [pdf]
  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 [ECCC]
  Irit Dinur and Prahladh Harsha.

• Smoothed Analysis of Multiobjective Optimization [pdf]
  Heiko Roeglin and Shang-Hua Teng.

• k-Means has Polynomial Smoothed Complexity [arXiv]
  David Arthur, Bodo Manthey and Heiko Roeglin.

• Reducibility Among Fractional Stability Problems [pdf] [ECCC] [arXiv]
  Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

• Online Stochastic Matching: Beating 1-1/e [pdf]
  Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.

• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems [arXiv]
  Sandy Irani and Daniel Gottesman.

• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities [arXiv]
  Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng.

• Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy [pdf]
  Yi Deng, Vipul Goyal and Amit Sahai.

• Space-Efficient Framework for Top-k String Retrieval Problems [pdf]
  Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter.

• (Meta) Kernelization [pdf]
  Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos.

• Choice-memory tradeoff in allocations [arXiv]
  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 [pdf]
  Andrea Montanari and Amin Saberi.

• Instance-Optimal Geometric Algorithms [ps]
  Peyman Afshani, Jeremy Barbay and Timothy M. Chan.

• Planarity allowing few error vertices in linear time [pdf]
  Ken-ichi Kawarabayashi.

• Constructing Small-Bias Sets from Algebraic-Geometric Codes [pdf]
  Avraham Ben-Aroya and Amnon Ta-Shma.

• Oblivious Routing for the L_p-norm [pdf]
  Matthias Englert and Harald Räcke.

• The Intersection of Two Halfspaces Has High Threshold Degree [ECCC] [arXiv]
  Alexander Sherstov.

• Distance Oracles for Sparse Graphs [html] [pdf]
  Christian Sommer, Elad Verbin and Wei Yu.

• Universal Blind Quantum Computation [arXiv]
  Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.

• Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization [arXiv]
  Tanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.

• Decomposing Coverings and the Planar Sensor Cover Problem [pdf]
  Matt Gibson and Kasturi Varadarajan.

• Extracting Correlations
  Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

• The Data Stream Space Complexity of Cascaded Norms [pdf]
  T.S. Jayram and David Woodruff.

• Faster generation of random spanning trees [pdf]
  Jonathan Kelner and Aleksander Madry.

• Integrality gaps for Strong SDP Relaxations of Unique Games [pdf]
  Prasad Raghavendra and David Steurer.

• How to Round Any CSP [pdf]
  Prasad Raghavendra and David Steurer.

• KKL, Kruskal-Katona, and monotone nets [pdf]
  Ryan O'Donnell and Karl Wimmer.

• Higher eigenvalues of graphs [pdf]
  Jonathan Kelner, James Lee, Gregory Price and Shanghua Teng.

• Efficient sketches for Earth-Mover Distance, with applications [pdf]
  Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.

• Agnostic Learning of Monomials by Halfspaces is Hard [pdf]
  Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.

• An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk [arXiv]
  Ashish Goel and Ian Post.

• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions [pdf]
  Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.

• Local Graph Partitions for Approximation and Testing [html]
  Avinatan Hassidim, Jonathan Kelner, Huy Nguyen and Krzysztof Onak.

• Linear systems over composite moduli [pdf]
  Arkadev Chattopadhyay and Avi Wigderson.

• Models for the compressible Web [pdf]
  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 [arXiv]
  Jonah Sherman.

• A Probabilistic Inequality with Applications to Threshold Direct Product Theorems [ECCC]
  Falk Unger.

• 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness [summary] [pdf]
  Yael Tauman Kalai, Xin Li and Anup Rao.

---------------------------------------------------------------------------------------