| 2009 | Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. | Venkatesan Guruswami |
| 2009 | Online and stochastic survivable network design. | Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi |
| 2009 | A constant-factor approximation for stochastic Steiner forest. | Anupam Gupta, Amit Kumar |
| 2009 | List decoding tensor products and interleaved codes. | Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra |
| 2009 | Athena lecture: Controlling Access to Programs? | Shafi Goldwasser |
| 2009 | On proximity oblivious testing. | Oded Goldreich, Dana Ron |
| 2009 | Universally utility-maximizing privacy mechanisms. | Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan |
| 2009 | Fully homomorphic encryption using ideal lattices. | Craig Gentry |
| 2009 | The extended BG-simulation and the characterization of t-resiliency. | Eli Gafni |
| 2009 | Near-perfect load balancing by randomized rounding. | Tobias Friedrich, Thomas Sauerwald |
| 2009 | Private coresets. | Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim |
| 2009 | On the convergence of regret minimization dynamics in concave games. | Eyal Even-Dar, Yishay Mansour, Uri Nadav |
| 2009 | 3-query locally decodable codes of subexponential length. | Klim Efremenko |
| 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 | Differential privacy and robust statistics. | Cynthia Dwork, Jing Lei |
| 2009 | Non-malleable extractors and symmetric key cryptography from weak secrets. | Yevgeniy Dodis, Daniel Wichs |
| 2009 | On cryptography with auxiliary input. | Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett |
| 2009 | Tight lower bounds for greedy routing in uniform small world rings. | Martin Dietzfelbinger, Philipp Woelfel |
| 2009 | On oblivious PTAS's for nash equilibrium. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 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 | Numerical linear algebra in the streaming model. | Kenneth L. Clarkson, David P. Woodruff |
| 2009 | A new approach to auctions and resilient mechanism design. | Jing Chen, Silvio Micali |
| 2009 | A deterministic reduction for the gap minimum distance problem: [extended abstract]. | Qi Cheng, Daqing Wan |
| 2009 | Fault-tolerant spanners for general graphs. | Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty |
| 2009 | Integrality gaps for Sherali-Adams relaxations. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |