| 2010 | Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification. | Hoeteck Wee |
| 2010 | The Complexity of Distributions. | Emanuele Viola |
| 2010 | Learning Convex Concepts from Gaussian Distributions with PCA. | Santosh S. Vempala |
| 2010 | Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. | Santosh S. Vempala |
| 2010 | Testing Properties of Sparse Images. | Gilad Tsur, Dana Ron |
| 2010 | Computational Transition at the Uniqueness Threshold. | Allan Sly |
| 2010 | Budget Feasible Mechanisms. | Yaron Singer |
| 2010 | Optimal Stochastic Planarization. | Anastasios Sidiropoulos |
| 2010 | From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits. | Nitin Saxena, C. Seshadhri |
| 2010 | Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. | Rahul Santhanam |
| 2010 | Estimating the Longest Increasing Sequence in Polylogarithmic Time. | Michael E. Saks, C. Seshadhri |
| 2010 | Improved Bounds for Geometric Permutations. | Natan Rubin, Haim Kaplan, Micha Sharir |
| 2010 | The Monotone Complexity of k-clique on Random Graphs. | Benjamin Rossman |
| 2010 | Bounds on Monotone Switching Networks for Directed Connectivity. | Aaron Potechin |
| 2010 | All-Pairs Shortest Paths in O(n | Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick |
| 2010 | Distance Oracles beyond the Thorup-Zwick Bound. | Mihai Patrascu, Liam Roditty |
| 2010 | Lower Bounds on Near Neighbor Search via Metric Expansion. | Rina Panigrahy, Kunal Talwar, Udi Wieder |
| 2010 | Settling the Polynomial Learnability of Mixtures of Gaussians. | Ankur Moitra, Gregory Valiant |
| 2010 | The Limits of Two-Party Differential Privacy. | Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan |
| 2010 | Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. | Konstantin Makarychev, Yury Makarychev |
| 2010 | On the Computational Complexity of Coin Flipping. | Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai |
| 2010 | Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs. | Aleksander Madry |
| 2010 | A Lower Bound for Dynamic Approximate Membership Data Structures. | Shachar Lovett, Ely Porat |
| 2010 | Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. | Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka |
| 2010 | On the Insecurity of Parallel Repetition for Leakage Resilience. | Allison B. Lewko, Brent Waters |