| 2009 | 3-query locally decodable codes of subexponential length. Klim Efremenko |
| 2009 | A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara |
| 2009 | A constant-factor approximation for stochastic Steiner forest. Anupam Gupta, Amit Kumar |
| 2009 | A constructive proof of the Lovász local lemma. Robin A. Moser |
| 2009 | A deterministic reduction for the gap minimum distance problem: [extended abstract]. Qi Cheng, Daqing Wan |
| 2009 | A fast and efficient algorithm for low-rank approximation of a matrix. Nam H. Nguyen, Thong T. Do, Trac D. Tran |
| 2009 | A nearly optimal oracle for avoiding failed vertices and edges. Aaron Bernstein, David R. Karger |
| 2009 | A new approach to auctions and resilient mechanism design. Jing Chen, Silvio Micali |
| 2009 | A new line of attack on the dichotomy conjecture. Gábor Kun, Mario Szegedy |
| 2009 | A unified framework for concurrent security: universal composability from stand-alone non-malleability. Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam |
| 2009 | Affiliation networks. Silvio Lattanzi, D. Sivakumar |
| 2009 | Affine dispersers from subspace polynomials. Eli Ben-Sasson, Swastik Kopparty |
| 2009 | An axiomatic approach to algebrization. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
| 2009 | An efficient algorithm for partial order production. Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro |
| 2009 | An improved constant-time approximation algorithm for maximum matchings. Yuichi Yoshida, Masaki Yamamoto, Hiro Ito |
| 2009 | Approximating edit distance in near-linear time. Alexandr Andoni, Krzysztof Onak |
| 2009 | Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. Venkatesan Guruswami |
| 2009 | Athena lecture: Controlling Access to Programs? Shafi Goldwasser |
| 2009 | Bit-probe lower bounds for succinct data structures. Emanuele Viola |
| 2009 | CSP gaps and reductions in the lasserre hierarchy. Madhur Tulsiani |
| 2009 | Conditional hardness for satisfiable 3-CSPs. Ryan O'Donnell, Yi Wu |
| 2009 | Differential privacy and robust statistics. Cynthia Dwork, Jing Lei |
| 2009 | Distributed (delta+1)-coloring in linear (in delta) time. Leonid Barenboim, Michael Elkin |
| 2009 | Efficient discrete-time simulations of continuous-time quantum query algorithms. Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando D. Somma, David L. Yonge-Mallo |
| 2009 | Every planar graph is the intersection graph of segments in the plane: extended abstract. Jérémie Chalopin, Daniel Gonçalves |
| 2009 | Exact learning of random DNF over the uniform distribution. Linda Sellie |
| 2009 | Explicit construction of a small epsilon-net for linear threshold functions. Yuval Rabani, Amir Shpilka |
| 2009 | Fault-tolerant spanners for general graphs. Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty |
| 2009 | Finding sparse cuts locally using evolving sets. Reid Andersen, Yuval Peres |
| 2009 | Finding, minimizing, and counting weighted subgraphs. Virginia Vassilevska, Ryan Williams |
| 2009 | Fully homomorphic encryption using ideal lattices. Craig Gentry |
| 2009 | Green's conjecture and testing linear-invariant properties. Asaf Shapira |
| 2009 | Hadwiger's conjecture is decidable. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2009 | Holant problems and counting CSP. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2009 | Homology flows, cohomology cuts. Erin W. Chambers, Jeff Erickson, Amir Nayyeri |
| 2009 | How long does it take to catch a wild kangaroo? Ravi Montenegro, Prasad Tetali |
| 2009 | Inaccessible entropy. Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee |
| 2009 | Integrality gaps for Sherali-Adams relaxations. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2009 | Intrinsic robustness of the price of anarchy. Tim Roughgarden |
| 2009 | Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. Marek Karpinski, Warren Schudy |
| 2009 | List decoding tensor products and interleaved codes. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra |
| 2009 | Max cut and the smallest eigenvalue. Luca Trevisan |
| 2009 | MaxMin allocation via degree lower-bounded arborescences. MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami |
| 2009 | Message passing algorithms and improved LP decoding. Sanjeev Arora, Constantinos Daskalakis, David Steurer |
| 2009 | Mixing time for the solid-on-solid model. Fabio Martinelli, Alistair Sinclair |
| 2009 | Multiple intents re-ranking. Yossi Azar, Iftah Gamzu, Xiaoxin Yin |
| 2009 | Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. Robert Kleinberg, Georgios Piliouras, Éva Tardos |
| 2009 | Near-perfect load balancing by randomized rounding. Tobias Friedrich, Thomas Sauerwald |
| 2009 | New direct-product testers and 2-query PCPs. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
| 2009 | Non-malleability amplification. Huijia Lin, Rafael Pass |
| 2009 | Non-malleable extractors and symmetric key cryptography from weak secrets. Yevgeniy Dodis, Daniel Wichs |
| 2009 | Non-monotone submodular maximization under matroid and knapsack constraints. Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko |
| 2009 | Numerical linear algebra in the streaming model. Kenneth L. Clarkson, David P. Woodruff |
| 2009 | On cryptography with auxiliary input. Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett |
| 2009 | On oblivious PTAS's for nash equilibrium. Constantinos Daskalakis, Christos H. Papadimitriou |
| 2009 | On proximity oblivious testing. Oded Goldreich, Dana Ron |
| 2009 | On the complexity of communication complexity. Eyal Kushilevitz, Enav Weinreb |
| 2009 | On the complexity of differentially private data release: efficient algorithms and hardness results. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan |
| 2009 | On the convergence of regret minimization dynamics in concave games. Eyal Even-Dar, Yishay Mansour, Uri Nadav |
| 2009 | On the geometry of graphs with a forbidden minor. James R. Lee, Anastasios Sidiropoulos |
| 2009 | Online and stochastic survivable network design. Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi |
| 2009 | Polynomial-time theory of matrix groups. László Babai, Robert Beals, Ákos Seress |
| 2009 | Private coresets. Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim |
| 2009 | Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 Michael Mitzenmacher |
| 2009 | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. Chris Peikert |
| 2009 | Quantum algorithms using the curvelet transform. Yi-Kai Liu |
| 2009 | Random graphs and the parity quantifier. Phokion G. Kolaitis, Swastik Kopparty |
| 2009 | Random walks on polytopes and an affine interior point method for linear programming. Ravi Kannan, Hariharan Narayanan |
| 2009 | Randomly supported independence and resistance. Per Austrin, Johan Håstad |
| 2009 | Reconstruction for the Potts model. Allan Sly |
| 2009 | Sherali-adams relaxations of the matching polytope. Claire Mathieu, Alistair Sinclair |
| 2009 | Short seed extractors against quantum storage. Amnon Ta-Shma |
| 2009 | Small-size epsilon-nets for axis-parallel rectangles and boxes. Boris Aronov, Esther Ezra, Micha Sharir |
| 2009 | Testing juntas nearly optimally. Eric Blais |
| 2009 | The detectability lemma and quantum gap amplification. Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2009 | The extended BG-simulation and the characterization of t-resiliency. Eli Gafni |
| 2009 | The work of Leslie Valiant. Avi Wigderson |
| 2009 | Tight lower bounds for greedy routing in uniform small world rings. Martin Dietzfelbinger, Philipp Woelfel |
| 2009 | Twice-ramanujan sparsifiers. Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava |
| 2009 | Universally utility-maximizing privacy mechanisms. Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan |