| 2006 | Zero knowledge with efficient provers. | Minh-Huyen Nguyen, Salil P. Vadhan |
| 2006 | Linear time low tree-width partitions and algorithmic consequences. | Jaroslav Nesetril, Patrice Ossona de Mendez |
| 2006 | Sub-constant error low degree test of almost-linear size. | Dana Moshkovitz, Ran Raz |
| 2006 | Local zero knowledge. | Silvio Micali, Rafael Pass |
| 2006 | Provably near-optimal sampling-based algorithms for Stochastic inventory control models. | Retsef Levi, Robin Roundy, David B. Shmoys |
| 2006 | Information-theoretically secure protocols and security under composition. | Eyal Kushilevitz, Yehuda Lindell, Tal Rabin |
| 2006 | A subset spanner for Planar graphs, : with application to subset TSP. | Philip N. Klein |
| 2006 | Graph partitioning using single commodity flows. | Rohit Khandekar, Satish Rao, Umesh V. Vazirani |
| 2006 | A randomized polynomial-time simplex algorithm for linear programming. | Jonathan A. Kelner, Daniel A. Spielman |
| 2006 | Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. | Ken-ichi Kawarabayashi, Bojan Mohar |
| 2006 | On earthmover distance, metric labeling, and 0-extension. | Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani |
| 2006 | Deterministic extractors for small-space sources. | Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman |
| 2006 | Black-box constructions for secure computation. | Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank |
| 2006 | Can every randomized algorithm be derandomized? | Russell Impagliazzo |
| 2006 | The effect of collusion in congestion games. | Ara Hayrapetyan, va Tardos, Tom Wexler |
| 2006 | Limitations of quantum coset states for graph isomorphism. | Sean Hallgren, Cristopher Moore, Martin Rtteler, Alexander Russell, Pranab Sen |
| 2006 | Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. | Leonid Gurvits |
| 2006 | Explicit capacity-achieving list-decodable codes. | Venkatesan Guruswami, Atri Rudra |
| 2006 | Reducibility among equilibrium problems. | Paul W. Goldberg, Christos H. Papadimitriou |
| 2006 | Bounded-error quantum state identification and exponential separations in communication complexity. | Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf |
| 2006 | Minimizing average flow time on related machines. | Naveen Garg, Amit Kumar |
| 2006 | Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. | Lisa Fleischer, Jochen Knemann, Stefano Leonardi, Guido Schfer |
| 2006 | Fast convergence to Wardrop equilibria by adaptive sampling methods. | Simon Fischer, Harald Rcke, Berthold Vcking |
| 2006 | Clique-width minimization is NP-hard. | Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider |
| 2006 | Hardness of approximate two-level logic minimization and PAC learning with membership queries. | Vitaly Feldman |