List of accepted papers for 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 Decision Trees From Random Examples: a Smoothed Analysis Adam Kalai, Shang-Hua Teng and Alex Samorodnitsky. 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 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.