| 2006 | On the time complexity of 2-tag systems and small universal Turing machines. | Damien Woods, Turlough Neary |
| 2006 | Lower Bounds for Additive Spanners, Emulators, and More. | David P. Woodruff |
| 2006 | On a Geometric Generalization of the Upper Bound Theorem. | Uli Wagner |
| 2006 | Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. | Roman Vershynin |
| 2006 | Accidental Algorithms. | Leslie G. Valiant |
| 2006 | Better lossless condensers through derandomized curve samplers. | Amnon Ta-Shma, Christopher Umans |
| 2006 | On the Quantum Query Complexity of Local Search in Two and Three Dimensions. | Xiaoming Sun, Andrew Chi-Chih Yao |
| 2006 | Improved Approximation Algorithms for Large Matrices via Random Projections. | Tams Sarls |
| 2006 | Norm of the inverse of a random matrix. | Mark Rudelson |
| 2006 | Postselection threshold against biased noise. | Ben Reichardt |
| 2006 | An Omega(n | Alexander A. Razborov, Sergey Yekhanin |
| 2006 | Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. | Luis Rademacher, Santosh S. Vempala |
| 2006 | Higher Lower Bounds for Near-Neighbor and Further Rich Problems. | Mihai Patrascu, Mikkel Thorup |
| 2006 | Planar Point Location in Sublogarithmic Time. | Mihai Patrascu |
| 2006 | The Effectiveness of Lloyd-Type Methods for the k-Means Problem. | Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy |
| 2006 | Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. | Krzysztof Onak, Pawel Parys |
| 2006 | Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. | Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan |
| 2006 | Planar Earthmover is not in L_1. | Assaf Naor, Gideon Schechtman |
| 2006 | Input-Indistinguishable Computation. | Silvio Micali, Rafael Pass, Alon Rosen |
| 2006 | Ramsey partitions and proximity data structures. | Manor Mendel, Assaf Naor |
| 2006 | Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. | Lszl Lovsz, Santosh S. Vempala |
| 2006 | Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. | James R. Lee, Assaf Naor |
| 2006 | Algorithms on negatively curved spaces. | Robert Krauthgamer, James R. Lee |
| 2006 | An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion. | Mikko Koivisto |
| 2006 | Cryptographic Hardness for Learning Intersections of Halfspaces. | Adam R. Klivans, Alexander A. Sherstov |