
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 spidercover decompositions
Zeev Nutov.
 Randomized SelfAssembly for Exact Shapes
David Doty.
 Symmetry and approximability of submodular maximization problems
Jan Vondrak.
 Fully Dynamic $(2 + \eps)$ Approximate AllPairs 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.
 Twomessage 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
DangTrinh HuynhNgoc and Paul Beame.
 Improved Approximation Algorithms for PrizeCollecting 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 ShangHua 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 MulticommodityType 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 VertexConnectivity 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 lowerror 2query PCPs using decodable PCPs
Irit Dinur and Prahladh Harsha.
 Smoothed Analysis of Multiobjective Optimization
Heiko Roeglin and ShangHua Teng.
 kMeans 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 ShangHua Teng.
 Online Stochastic Matching: Beating 11/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 ArrowDebreu Equilibria in Markets with Additively Separable Utilities
Xi Chen, Decheng Dai, Ye Du and ShangHua Teng.
 Resolving the Simultaneous Resettability Conjecture and a New NonBlackBox Simulation Strategy
Yi Deng, Vipul Goyal and Amit Sahai.
 SpaceEfficient Framework for Topk 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.
 Choicememory tradeoff in allocations
Noga Alon, Ori GurelGurevich and Eyal Lubetzky.
 The Communication Complexity of SetDisjointness with Small Sets and 01 Intersection
Eyal Kushilevitz and Enav Weinreb.
 Convergence to Equilibrium in Local Interaction Games
Andrea Montanari and Amin Saberi.
 InstanceOptimal Geometric Algorithms
Peyman Afshani, Jeremy Barbay and Timothy M. Chan.
 Planarity allowing few error vertices in linear time
Kenichi Kawarabayashi.
 Constructing SmallBias Sets from AlgebraicGeometric Codes
Avraham BenAroya and Amnon TaShma.
 Oblivious Routing for the L_pnorm
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 NonUniform 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, KruskalKatona, 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 EarthMover 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 BuyatBulk
Ashish Goel and Ian Post.
 Approximability of Combinatorial Problems with Multiagent 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.
 2Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness
Yael Tauman Kalai, Xin Li and Anup Rao.
