| 2006 | On the importance of idempotence. | Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2006 | New approximation guarantee for chromatic number. | Sanjeev Arora, Eden Chlamtac |
| 2006 | Fast leader-election protocols with bounded cheaters' edge. | Spyridon Antonakopoulos |
| 2006 | Learning a circuit by injecting values. | Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu |
| 2006 | Logarithmic hardness of the directed congestion minimization problem. | Matthew Andrews, Lisa Zhang |
| 2006 | A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. | Andris Ambainis, Robert Spalek, Ronald de Wolf |
| 2006 | On basing one-way functions on NP-hardness. | Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz |
| 2006 | Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. | Nir Ailon, Bernard Chazelle |
| 2006 | A polynomial quantum algorithm for approximating the Jones polynomial. | Dorit Aharonov, Vaughan Jones, Zeph Landau |
| 2006 | On the solution-space geometry of random constraint satisfaction problems. | Dimitris Achlioptas, Federico Ricci-Tersenghi |
| 2006 | Advances in metric embedding theory. | Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2005 | On obfuscating point functions. | Hoeteck Wee |
| 2005 | Spectral norm of random matrices. | Van H. Vu |
| 2005 | Tensor decomposition and approximation schemes for constraint satisfaction problems. | Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala |
| 2005 | An O(log n log log n) space algorithm for undirected st-connectivity. | Vladimir Trifonov |
| 2005 | On uniform amplification of hardness in NP. | Luca Trevisan |
| 2005 | Worst-case update times for fully-dynamic all-pairs shortest paths. | Mikkel Thorup |
| 2005 | On random pm 1 matrices: singularity and determinant. | Terence Tao, Van H. Vu |
| 2005 | Tensor norms and the classical communication complexity of nonlocal quantum measurement. | Yaoyun Shi |
| 2005 | Polynomial time quantum algorithm for the computation of the unit group of a number field. | Arthur Schmidt, Ulrich Vollmer |
| 2005 | How to spread adversarial nodes?: rotate! | Christian Scheideler |
| 2005 | The round complexity of two-party random selection. | Saurabh Sanghvi, Salil P. Vadhan |
| 2005 | Testing monotone high-dimensional distributions. | Ronitt Rubinfeld, Rocco A. Servedio |
| 2005 | Undirected ST-connectivity in log-space. | Omer Reingold |
| 2005 | On lattices, learning with errors, random linear codes, and cryptography. | Oded Regev |