| 2009 | Bounded Independence Fools Halfspaces. | Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola |
| 2009 | Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy. | Yi Deng, Vipul Goyal, Amit Sahai |
| 2009 | An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. | Julia Chuzhoy, Sanjeev Khanna |
| 2009 | Models for the Compressible Web. | Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Prabhakar Raghavan |
| 2009 | Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. | Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng |
| 2009 | A (log n) | Jeff Cheeger, Bruce Kleiner, Assaf Naor |
| 2009 | Linear Systems over Composite Moduli. | Arkadev Chattopadhyay, Avi Wigderson |
| 2009 | Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. | Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna |
| 2009 | On Allocating Goods to Maximize Fairness. | Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna |
| 2009 | Optimal Quantum Strong Coin Flipping. | Andr Chailloux, Iordanis Kerenidis |
| 2009 | Delaunay Triangulations in O(sort(n)) Time and More. | Kevin Buchin, Wolfgang Mulzer |
| 2009 | Universal Blind Quantum Computation. | Anne Broadbent, Joseph F. Fitzsimons, Elham Kashefi |
| 2009 | (Meta) Kernelization. | Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos |
| 2009 | Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time. | Aaron Bernstein |
| 2009 | Constructing Small-Bias Sets from Algebraic-Geometric Codes. | Avraham Ben-Aroya, Amnon Ta-Shma |
| 2009 | Multiparty Communication Complexity and Threshold Circuit Size of AC^0. | Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2009 | Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem. | Saugata Basu, Thierry Zell |
| 2009 | Constraint Satisfaction Problems of Bounded Width. | Libor Barto, Marcin Kozik |
| 2009 | Regularity Lemmas and Combinatorial Algorithms. | Nikhil Bansal, Ryan Williams |
| 2009 | Optimal Long Code Test with One Free Bit. | Nikhil Bansal, Subhash Khot |
| 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 | k-Means Has Polynomial Smoothed Complexity. | David Arthur, Bodo Manthey, Heiko Rglin |
| 2009 | Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP. | Aaron Archer, MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Howard J. Karloff |
| 2009 | Efficient Sketches for Earth-Mover Distance, with Applications. | Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff |
| 2009 | Choice-Memory Tradeoff in Allocations. | Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich |