| 2006 | Finding small balanced separators. | Uriel Feige, Mohammad Mahdian |
| 2006 | On maximizing welfare when utility functions are subadditive. | Uriel Feige |
| 2006 | Time-space tradeoffs for implementations of snapshots. | Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert |
| 2006 | On the randomness complexity of efficient sampling. | Bella Dubrov, Yuval Ishai |
| 2006 | Truthful randomized mechanisms for combinatorial auctions. | Shahar Dobzinski, Noam Nisan, Michael Schapira |
| 2006 | Conditional hardness for approximate coloring. | Irit Dinur, Elchanan Mossel, Oded Regev |
| 2006 | On the fourier tails of bounded functions over the discrete cube. | Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell |
| 2006 | The PCP theorem by gap amplification. | Irit Dinur |
| 2006 | Integrality gaps for sparsest cut and minimum linear arrangement problems. | Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi |
| 2006 | Online trading algorithms and robust option pricing. | Peter M. DeMarzo, Ilan Kremer, Yishay Mansour |
| 2006 | Optimal phylogenetic reconstruction. | Constantinos Daskalakis, Elchanan Mossel, Sbastien Roch |
| 2006 | The complexity of computing a Nash equilibrium. | Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou |
| 2006 | Searching dynamic point sets in spaces with bounded doubling dimension. | Richard Cole, Lee-Ad Gottlieb |
| 2006 | Building triangulations using epsilon-nets. | Kenneth L. Clarkson |
| 2006 | Hardness of cut problems in directed graphs. | Julia Chuzhoy, Sanjeev Khanna |
| 2006 | Pricing for fairness: distributed resource allocation for multiple objectives. | Sung-woo Cho, Ashish Goel |
| 2006 | Edge-disjoint paths in Planar graphs with constant congestion. | Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2006 | Near-optimal algorithms for unique games. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | Graph limits and parameter testing. | Christian Borgs, Jennifer T. Chayes, Lszl Lovsz, Vera T. Ss, Balzs Szegedy, Katalin Vesztergombi |
| 2006 | Byzantine agreement in the full-information model in O(log n) rounds. | Michael Ben-Or, Elan Pavlov, Vinod Vaikuntanathan |
| 2006 | Private approximation of search problems. | Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb |
| 2006 | 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. | Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson |
| 2006 | The Santa Claus problem. | Nikhil Bansal, Maxim Sviridenko |
| 2006 | A quasi-PTAS for unsplittable flow on line graphs. | Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber |
| 2006 | The distance trisector curve. | Tetsuo Asano, Jir Matousek, Takeshi Tokuyama |