| 2010 | Frugal Mechanism Design via Spectral Techniques. | Ning Chen, Edith Elkind, Nick Gravin, Fedor Petrov |
| 2010 | Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. | Chandra Chekuri, Jan Vondrk, Rico Zenklusen |
| 2010 | Vertex Sparsifiers and Abstract Rounding Algorithms. | Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra |
| 2010 | Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. | Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor |
| 2010 | Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions. | Ran Canetti, Huijia Lin, Rafael Pass |
| 2010 | Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2010 | A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. | Jin-yi Cai, Xi Chen |
| 2010 | The Coin Problem and Pseudorandomness for Branching Programs. | Joshua Brody, Elad Verbin |
| 2010 | Impossibility of Differentially Private Universally Optimal Mechanisms. | Hai Brenner, Kobbi Nissim |
| 2010 | Pseudorandom Generators for Regular Branching Programs. | Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff |
| 2010 | Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage. | Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan |
| 2010 | The Sub-exponential Upper Bound for On-Line Chain Partitioning. | Bartlomiej Bosek, Tomasz Krawczyk |
| 2010 | Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. | Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen |
| 2010 | Determinant Sums for Undirected Hamiltonicity. | Andreas Bjrklund |
| 2010 | Optimal Testing of Reed-Muller Codes. | Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman |
| 2010 | A Unified Framework for Testing Linear-Invariant Properties. | Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira |
| 2010 | Local List Decoding with a Constant Number of Queries. | Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma |
| 2010 | Polynomial Learning of Distribution Families. | Mikhail Belkin, Kaushik Sinha |
| 2010 | On the Queue Number of Planar Graphs. | Giuseppe Di Battista, Fabrizio Frati, Jnos Pach |
| 2010 | The Geometry of Scheduling. | Nikhil Bansal, Kirk Pruhs |
| 2010 | Constructive Algorithms for Discrepancy Minimization. | Nikhil Bansal |
| 2010 | Stability Yields a PTAS for k-Median and k-Means Clustering. | Pranjal Awasthi, Avrim Blum, Or Sheffet |
| 2010 | Subexponential Algorithms for Unique Games and Related Problems. | Sanjeev Arora, Boaz Barak, David Steurer |
| 2010 | Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. | Yuriy Arbitman, Moni Naor, Gil Segev |
| 2010 | Minimum-Cost Network Design with (Dis)economies of Scale. | Matthew Andrews, Spyridon Antonakopoulos, Lisa Zhang |