| 2010 | Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction. | Renato Paes Leme, va Tardos |
| 2010 | Clustering with Spectral Norm and the k-Means Algorithm. | Amit Kumar, Ravindran Kannan |
| 2010 | Approaching Optimality for Solving SDD Linear Systems. | Ioannis Koutis, Gary L. Miller, Richard Peng |
| 2010 | Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts. | David Kempe, Mahyar Salek, Cristopher Moore |
| 2010 | A Separator Theorem in Minor-Closed Classes. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2010 | The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem. | Marcus Isaksson, Guy Kindler, Elchanan Mossel |
| 2010 | An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games. | Aram W. Harrow, Ashley Montanaro |
| 2010 | A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. | Moritz Hardt, Guy N. Rothblum |
| 2010 | New Constructive Aspects of the Lovasz Local Lemma. | Bernhard Haeupler, Barna Saha, Aravind Srinivasan |
| 2010 | Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. | Venkatesan Guruswami, Adam D. Smith |
| 2010 | Sequential Rationality in Cryptographic Protocols. | Ronen Gradwohl, Noam Livne, Alon Rosen |
| 2010 | A Fourier-Analytic Approach to Reed-Muller Decoding. | Parikshit Gopalan |
| 2010 | One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk. | Ashish Goel, Ian Post |
| 2010 | Logspace Versions of the Theorems of Bodlaender and Courcelle. | Michael Elberfeld, Andreas Jakoby, Till Tantau |
| 2010 | Boosting and Differential Privacy. | Cynthia Dwork, Guy N. Rothblum, Salil P. Vadhan |
| 2010 | Deciding First-Order Properties for Sparse Graphs. | Zdenek Dvork, Daniel Krl, Robin Thomas |
| 2010 | Matching Vector Codes. | Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin |
| 2010 | Black-Box Randomized Reductions in Algorithmic Mechanism Design. | Shaddin Dughmi, Tim Roughgarden |
| 2010 | Approximating Maximum Weight Matching in Near-Linear Time. | Ran Duan, Seth Pettie |
| 2010 | Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature. | David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers |
| 2010 | Cryptography against Continuous Memory Attacks. | Yevgeniy Dodis, Kristiyan Haralambiev, Adriana Lpez-Alt, Daniel Wichs |
| 2010 | Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. | Irit Dinur, Subhash Khot, Will Perkins, Muli Safra |
| 2010 | Bounded Independence Fools Degree-2 Threshold Functions. | Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson |
| 2010 | Efficient Volume Sampling for Row/Column Subset Selection. | Amit Deshpande, Luis Rademacher |
| 2010 | Sublinear Optimization for Machine Learning. | Kenneth L. Clarkson, Elad Hazan, David P. Woodruff |