| 2010 | Pseudorandom generators for polynomial threshold functions. | Raghu Meka, David Zuckerman |
| 2010 | Tractable hypergraph properties for constraint satisfaction and conjunctive queries. | Dniel Marx |
| 2010 | Recognizing well-parenthesized expressions in the streaming model. | Frdric Magniez, Claire Mathieu, Ashwin Nayak |
| 2010 | Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. | Aleksander Madry |
| 2010 | Saving space by algebraization. | Daniel Lokshtanov, Jesper Nederlof |
| 2010 | Extensions and limits to vertex sparsification. | Frank Thomson Leighton, Ankur Moitra |
| 2010 | Matroid matching: the power of local search. | Jon Lee, Maxim Sviridenko, Jan Vondrk |
| 2010 | Bilipschitz snowflakes and metrics of negative type. | James R. Lee, Mohammad Moharrami |
| 2010 | Distributed computation in dynamic networks. | Fabian Kuhn, Nancy A. Lynch, Rotem Oshman |
| 2010 | Local list-decoding and testing of random linear codes from high error. | Swastik Kopparty, Shubhangi Saraf |
| 2010 | Subgraph sparsification and nearly optimal ultrasparsifiers. | Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng |
| 2010 | A strong direct product theorem for disjointness. | Hartmut Klauck |
| 2010 | A shorter proof of the graph minor algorithm: the unique linkage theorem. | Ken-ichi Kawarabayashi, Paul Wollan |
| 2010 | Odd cycle packing. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2010 | Complexity theory for operators in analysis. | Akitoshi Kawamura, Stephen A. Cook |
| 2010 | The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. | Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith, Jonathan R. Ullman |
| 2010 | Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. | Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich |
| 2010 | Spectral methods for matrices and tensors. | Ravindran Kannan |
| 2010 | Efficiently learning mixtures of two Gaussians. | Adam Tauman Kalai, Ankur Moitra, Gregory Valiant |
| 2010 | QIP = PSPACE. | Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous |
| 2010 | Non-commutative circuits and the sum-of-squares problem. | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
| 2010 | The maximum multiflow problems with bounded fractionality. | Hiroshi Hirai |
| 2010 | Bayesian algorithmic mechanism design. | Jason D. Hartline, Brendan Lucier |
| 2010 | An invariance principle for polytopes. | Prahladh Harsha, Adam R. Klivans, Raghu Meka |
| 2010 | On the geometry of differential privacy. | Moritz Hardt, Kunal Talwar |