| 2006 | Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. | Tams Kirly, Lap Chi Lau |
| 2006 | Towards Secure and Scalable Computation in Peer-to-Peer Networks. | Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2006 | SDP gaps and UGC-hardness for MAXCUTGAIN. | Subhash Khot, Ryan O'Donnell |
| 2006 | Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. | Yael Tauman Kalai, Ran Raz |
| 2006 | Cryptography from Anonymity. | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2006 | Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets |
| 2006 | A simple condition implying rapid mixing of single-site dynamics on spin systems. | Thomas P. Hayes |
| 2006 | Algebraic Structures and Algorithms for Matching and Matroid Problems. | Nicholas J. A. Harvey |
| 2006 | On the Compressibility of NP Instances and Cryptographic Applications. | Danny Harnik, Moni Naor |
| 2006 | Hardness of Learning Halfspaces with Noise. | Venkatesan Guruswami, Prasad Raghavendra |
| 2006 | Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. | Venkatesan Guruswami, Anindya C. Patthak |
| 2006 | Points on Computable Curves. | Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo |
| 2006 | Fault-Tolerant Distributed Computing in Full-Information Networks. | Shafi Goldwasser, Elan Pavlov, Vinod Vaikuntanathan |
| 2006 | Minimum Bounded Degree Spanning Trees. | Michel X. Goemans |
| 2006 | Explicit Exclusive Set Systems with Applications to Broadcast Encryption. | Craig Gentry, Zulfikar Ramzan, David P. Woodruff |
| 2006 | New Results for Learning Noisy Parities and Halfspaces. | Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami |
| 2006 | Coresets forWeighted Facilities and Their Applications. | Dan Feldman, Amos Fiat, Micha Sharir |
| 2006 | Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. | Uriel Feige, Jan Vondrk |
| 2006 | Witnesses for non-satisfiability of dense random 3CNF formulas. | Uriel Feige, Jeong Han Kim, Eran Ofek |
| 2006 | A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. | Toms Feder, Adam Guetz, Milena Mihail, Amin Saberi |
| 2006 | Balanced Allocations of Cake. | Jeff Edmonds, Kirk Pruhs |
| 2006 | How to Play Unique Games Using Embeddings. | Eden Chlamtac, Konstantin Makarychev, Yury Makarychev |
| 2006 | Computing Nash Equilibria: Approximation and Smoothed Complexity. | Xi Chen, Xiaotie Deng, Shang-Hua Teng |
| 2006 | Settling the Complexity of Two-Player Nash Equilibrium. | Xi Chen, Xiaotie Deng |
| 2006 | Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. | Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour |