| 2009 | (Meta) Kernelization. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos |
| 2009 | 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness. Yael Tauman Kalai, Xin Li, Anup Rao |
| 2009 | 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, 2009 |
| 2009 | A (log n) Jeff Cheeger, Bruce Kleiner, Assaf Naor |
| 2009 | A Complete Characterization of Statistical Query Learning with Applications to Evolvability. Vitaly Feldman |
| 2009 | A New Probability Inequality Using Typical Moments and Concentration Results. Ravindran Kannan |
| 2009 | A Parallel Repetition Theorem for Any Interactive Argument. Iftach Haitner |
| 2009 | A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. Falk Unger |
| 2009 | Agnostic Learning of Monomials by Halfspaces Is Hard. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu |
| 2009 | An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna |
| 2009 | An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk. Ashish Goel, Ian Post |
| 2009 | Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions. Gagan Goel, Chinmay Karande, Pushkar Tripathi, Lei Wang |
| 2009 | Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions. Zeev Nutov |
| 2009 | Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. Ankur Moitra |
| 2009 | Bit Encryption Is Complete. Steven A. Myers, Abhi Shelat |
| 2009 | Blackbox Polynomial Identity Testing for Depth 3 Circuits. Neeraj Kayal, Shubhangi Saraf |
| 2009 | Bounded Independence Fools Halfspaces. Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola |
| 2009 | Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut. Jonah Sherman |
| 2009 | Choice-Memory Tradeoff in Allocations. Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich |
| 2009 | Combinatorial PCPs with Efficient Verifiers. Or Meir |
| 2009 | Composition of Low-Error 2-Query PCPs Using Decodable PCPs. Irit Dinur, Prahladh Harsha |
| 2009 | Constraint Satisfaction Problems of Bounded Width. Libor Barto, Marcin Kozik |
| 2009 | Constructing Small-Bias Sets from Algebraic-Geometric Codes. Avraham Ben-Aroya, Amnon Ta-Shma |
| 2009 | Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks. Yossi Azar, Benjamin E. Birnbaum, L. Elisa Celis, Nikhil R. Devanur, Yuval Peres |
| 2009 | Convergence to Equilibrium in Local Interaction Games. Andrea Montanari, Amin Saberi |
| 2009 | Decomposing Coverings and the Planar Sensor Cover Problem. Matt Gibson, Kasturi R. Varadarajan |
| 2009 | Delaunay Triangulations in O(sort(n)) Time and More. Kevin Buchin, Wolfgang Mulzer |
| 2009 | Distance Oracles for Sparse Graphs. Christian Sommer, Elad Verbin, Wei Yu |
| 2009 | Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna |
| 2009 | Efficient Sketches for Earth-Mover Distance, with Applications. Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff |
| 2009 | Exact and Approximate Pattern Matching in the Streaming Model. Benny Porat, Ely Porat |
| 2009 | Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan |
| 2009 | Extracting Correlations. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2009 | Faster Generation of Random Spanning Trees. Jonathan A. Kelner, Aleksander Madry |
| 2009 | Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time. Aaron Bernstein |
| 2009 | Higher Eigenvalues of Graphs. Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng |
| 2009 | How to Round Any CSP. Prasad Raghavendra, David Steurer |
| 2009 | Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP. Aaron Archer, MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Howard J. Karloff |
| 2009 | Instance-Optimal Geometric Algorithms. Peyman Afshani, Jérémy Barbay, Timothy M. Chan |
| 2009 | Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. Prasad Raghavendra, David Steurer |
| 2009 | KKL, Kruskal-Katona, and Monotone Nets. Ryan O'Donnell, Karl Wimmer |
| 2009 | Learning and Smoothed Analysis. Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng |
| 2009 | Linear Systems over Composite Moduli. Arkadev Chattopadhyay, Avi Wigderson |
| 2009 | Local Graph Partitions for Approximation and Testing. Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak |
| 2009 | Models for the Compressible Web. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Prabhakar Raghavan |
| 2009 | Multiparty Communication Complexity and Threshold Circuit Size of AC^0. Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2009 | Oblivious Routing for the Lp-norm. Matthias Englert, Harald Räcke |
| 2009 | On Allocating Goods to Maximize Fairness. Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna |
| 2009 | On the Power of Randomization in Algorithmic Mechanism Design. Shahar Dobzinski, Shaddin Dughmi |
| 2009 | Online Stochastic Matching: Beating 1-1/e. Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, S. Muthukrishnan |
| 2009 | Optimal Long Code Test with One Free Bit. Nikhil Bansal, Subhash Khot |
| 2009 | Optimal Quantum Strong Coin Flipping. André Chailloux, Iordanis Kerenidis |
| 2009 | Orthogonal Range Reporting in Three and Higher Dimensions. Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen |
| 2009 | Planarity Allowing Few Error Vertices in Linear Time. Ken-ichi Kawarabayashi |
| 2009 | Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem. Saugata Basu, Thierry Zell |
| 2009 | Randomized Self-Assembly for Exact Shapes. David Doty |
| 2009 | Reducibility among Fractional Stability Problems. Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng |
| 2009 | Regularity Lemmas and Combinatorial Algorithms. Nikhil Bansal, Ryan Williams |
| 2009 | Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy. Yi Deng, Vipul Goyal, Amit Sahai |
| 2009 | SDP Integrality Gaps with Local ell_1-Embeddability. Subhash Khot, Rishi Saket |
| 2009 | Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng |
| 2009 | Smoothed Analysis of Multiobjective Optimization. Heiko Röglin, Shang-Hua Teng |
| 2009 | Space-Efficient Framework for Top-k String Retrieval Problems. Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter |
| 2009 | Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. Ben Reichardt |
| 2009 | Submodular Function Minimization under Covering Constraints. Satoru Iwata, Kiyohito Nagano |
| 2009 | Symmetry and Approximability of Submodular Maximization Problems. Jan Vondrák |
| 2009 | The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection. Eyal Kushilevitz, Enav Weinreb |
| 2009 | The Complexity of Rationalizing Network Formation. Shankar Kalyanaraman, Christopher Umans |
| 2009 | The Data Stream Space Complexity of Cascaded Norms. T. S. Jayram, David P. Woodruff |
| 2009 | The Intersection of Two Halfspaces Has High Threshold Degree. Alexander A. Sherstov |
| 2009 | The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. Daniel Gottesman, Sandy Irani |
| 2009 | Two-Message Quantum Interactive Proofs Are in PSPACE. Rahul Jain, Sarvagya Upadhyay, John Watrous |
| 2009 | Universal Blind Quantum Computation. Anne Broadbent, Joseph F. Fitzsimons, Elham Kashefi |
| 2009 | k-Means Has Polynomial Smoothed Complexity. David Arthur, Bodo Manthey, Heiko Röglin |