| 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 | A combinatorial characterization of the testable graph properties: it's all about regularity. Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira |
| 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 | A polynomial quantum algorithm for approximating the Jones polynomial. Dorit Aharonov, Vaughan Jones, Zeph Landau |
| 2006 | A quasi-PTAS for unsplittable flow on line graphs. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber |
| 2006 | A quasi-polynomial time approximation scheme for minimum weight triangulation. Jan Remy, Angelika Steger |
| 2006 | A randomized polynomial-time simplex algorithm for linear programming. Jonathan A. Kelner, Daniel A. Spielman |
| 2006 | A subset spanner for Planar graphs, : with application to subset TSP. Philip N. Klein |
| 2006 | Advances in metric embedding theory. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2006 | An efficient algorithm for solving word equations. Wojciech Plandowski |
| 2006 | Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. Nir Ailon, Bernard Chazelle |
| 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 | Black-box constructions for secure computation. Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank |
| 2006 | Bounded-error quantum state identification and exponential separations in communication complexity. Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf |
| 2006 | Building triangulations using epsilon-nets. Kenneth L. Clarkson |
| 2006 | Byzantine agreement in the full-information model in O(log n) rounds. Michael Ben-Or, Elan Pavlov, Vinod Vaikuntanathan |
| 2006 | Can every randomized algorithm be derandomized? Russell Impagliazzo |
| 2006 | Clique-width minimization is NP-hard. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider |
| 2006 | Conditional hardness for approximate coloring. Irit Dinur, Elchanan Mossel, Oded Regev |
| 2006 | Counting independent sets up to the tree threshold. Dror Weitz |
| 2006 | Deterministic extractors for small-space sources. Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman |
| 2006 | Edge-disjoint paths in Planar graphs with constant congestion. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2006 | Explicit capacity-achieving list-decodable codes. Venkatesan Guruswami, Atri Rudra |
| 2006 | Extractors for a constant number of polynomially small min-entropy independent sources. Anup Rao |
| 2006 | Fast convergence to Wardrop equilibria by adaptive sampling methods. Simon Fischer, Harald Räcke, Berthold Vöcking |
| 2006 | Fast leader-election protocols with bounded cheaters' edge. Spyridon Antonakopoulos |
| 2006 | Finding a maximum weight triangle in n Virginia Vassilevska, Ryan Williams |
| 2006 | Finding small balanced separators. Uriel Feige, Mohammad Mahdian |
| 2006 | Gowers uniformity, influence of variables, and PCPs. Alex Samorodnitsky, Luca Trevisan |
| 2006 | Graph limits and parameter testing. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, Katalin Vesztergombi |
| 2006 | Graph partitioning using single commodity flows. Rohit Khandekar, Satish Rao, Umesh V. Vazirani |
| 2006 | Hardness of approximate two-level logic minimization and PAC learning with membership queries. Vitaly Feldman |
| 2006 | Hardness of cut problems in directed graphs. Julia Chuzhoy, Sanjeev Khanna |
| 2006 | Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. Leonid Gurvits |
| 2006 | Information-theoretically secure protocols and security under composition. Eyal Kushilevitz, Yehuda Lindell, Tal Rabin |
| 2006 | Integrality gaps for sparsest cut and minimum linear arrangement problems. Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi |
| 2006 | Lattice problems and norm embeddings. Oded Regev, Ricky Rosen |
| 2006 | Learning a circuit by injecting values. Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu |
| 2006 | Limitations of quantum coset states for graph isomorphism. Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen |
| 2006 | Linear degree extractors and the inapproximability of max clique and chromatic number. David Zuckerman |
| 2006 | Linear time low tree-width partitions and algorithmic consequences. Jaroslav Nesetril, Patrice Ossona de Mendez |
| 2006 | Local zero knowledge. Silvio Micali, Rafael Pass |
| 2006 | Logarithmic hardness of the directed congestion minimization problem. Matthew Andrews, Lisa Zhang |
| 2006 | Minimizing average flow time on related machines. Naveen Garg, Amit Kumar |
| 2006 | Narrow proofs may be spacious: separating space and width in resolution. Jakob Nordström |
| 2006 | Near-optimal algorithms for unique games. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | New approximation guarantee for chromatic number. Sanjeev Arora, Eden Chlamtac |
| 2006 | New trade-offs in cost-sharing mechanisms. Tim Roughgarden, Mukund Sundararajan |
| 2006 | New upper and lower bounds for randomized and quantum local search. Shengyu Zhang |
| 2006 | On adequate performance measures for paging. Konstantinos Panagiotou, Alexander Souza |
| 2006 | On basing one-way functions on NP-hardness. Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz |
| 2006 | On earthmover distance, metric labeling, and 0-extension. Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani |
| 2006 | On maximizing welfare when utility functions are subadditive. Uriel Feige |
| 2006 | On the fourier tails of bounded functions over the discrete cube. Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell |
| 2006 | On the importance of idempotence. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2006 | On the randomness complexity of efficient sampling. Bella Dubrov, Yuval Ishai |
| 2006 | On the solution-space geometry of random constraint satisfaction problems. Dimitris Achlioptas, Federico Ricci-Tersenghi |
| 2006 | Online trading algorithms and robust option pricing. Peter M. DeMarzo, Ilan Kremer, Yishay Mansour |
| 2006 | Optimal phylogenetic reconstruction. Constantinos Daskalakis, Elchanan Mossel, Sébastien Roch |
| 2006 | Pricing for fairness: distributed resource allocation for multiple objectives. Sung-woo Cho, Ashish Goel |
| 2006 | Private approximation of search problems. Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb |
| 2006 | Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006 Jon M. Kleinberg |
| 2006 | Provably near-optimal sampling-based algorithms for Stochastic inventory control models. Retsef Levi, Robin Roundy, David B. Shmoys |
| 2006 | Pseudorandom walks on regular digraphs and the RL vs. L problem. Omer Reingold, Luca Trevisan, Salil P. Vadhan |
| 2006 | Reducibility among equilibrium problems. Paul W. Goldberg, Christos H. Papadimitriou |
| 2006 | Searching dynamic point sets in spaces with bounded doubling dimension. Richard Cole, Lee-Ad Gottlieb |
| 2006 | Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer |
| 2006 | Sub-constant error low degree test of almost-linear size. Dana Moshkovitz, Ran Raz |
| 2006 | The DLT priority sampling is essentially optimal. Mario Szegedy |
| 2006 | The PCP theorem by gap amplification. Irit Dinur |
| 2006 | The Santa Claus problem. Nikhil Bansal, Maxim Sviridenko |
| 2006 | The changing face of web search: algorithms, auctions and advertising. Prabhakar Raghavan |
| 2006 | The complexity of computing a Nash equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou |
| 2006 | The distance trisector curve. Tetsuo Asano, Jirí Matousek, Takeshi Tokuyama |
| 2006 | The effect of collusion in congestion games. Ara Hayrapetyan, Éva Tardos, Tom Wexler |
| 2006 | Time-space trade-offs for predecessor search. Mihai Patrascu, Mikkel Thorup |
| 2006 | Time-space tradeoffs for implementations of snapshots. Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert |
| 2006 | Truthful randomized mechanisms for combinatorial auctions. Shahar Dobzinski, Noam Nisan, Michael Schapira |
| 2006 | Zero knowledge with efficient provers. Minh-Huyen Nguyen, Salil P. Vadhan |
| 2006 | Zero-knowledge against quantum attacks. John Watrous |