| 2006 | 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings |
| 2006 | A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. Tomás Feder, Adam Guetz, Milena Mihail, Amin Saberi |
| 2006 | A simple condition implying rapid mixing of single-site dynamics on spin systems. Thomas P. Hayes |
| 2006 | Accidental Algorithms. Leslie G. Valiant |
| 2006 | Algebraic Structures and Algorithms for Matching and Matroid Problems. Nicholas J. A. Harvey |
| 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 | An Omega(n Alexander A. Razborov, Sergey Yekhanin |
| 2006 | Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. Tamás Király, Lap Chi Lau |
| 2006 | Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets |
| 2006 | Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour |
| 2006 | Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. Uriel Feige, Jan Vondrák |
| 2006 | Balanced Allocations of Cake. Jeff Edmonds, Kirk Pruhs |
| 2006 | Better lossless condensers through derandomized curve samplers. Amnon Ta-Shma, Christopher Umans |
| 2006 | Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. Roman Vershynin |
| 2006 | Computing Nash Equilibria: Approximation and Smoothed Complexity. Xi Chen, Xiaotie Deng, Shang-Hua Teng |
| 2006 | Concurrent Non-Malleable Zero Knowledge. Boaz Barak, Manoj Prabhakaran, Amit Sahai |
| 2006 | Coresets forWeighted Facilities and Their Applications. Dan Feldman, Amos Fiat, Micha Sharir |
| 2006 | Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. Venkatesan Guruswami, Anindya C. Patthak |
| 2006 | Cryptographic Hardness for Learning Intersections of Halfspaces. Adam R. Klivans, Alexander A. Sherstov |
| 2006 | Cryptography from Anonymity. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2006 | Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Luis Rademacher, Santosh S. Vempala |
| 2006 | Explicit Exclusive Set Systems with Applications to Broadcast Encryption. Craig Gentry, Zulfikar Ramzan, David P. Woodruff |
| 2006 | Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. László Lovász, Santosh S. Vempala |
| 2006 | Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths. Surender Baswana, Telikepalli Kavitha |
| 2006 | Fault-Tolerant Distributed Computing in Full-Information Networks. Shafi Goldwasser, Elan Pavlov, Vinod Vaikuntanathan |
| 2006 | Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. Krzysztof Onak, Pawel Parys |
| 2006 | Hardness of Learning Halfspaces with Noise. Venkatesan Guruswami, Prasad Raghavendra |
| 2006 | Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. Mikhail Belkin, Hariharan Narayanan, Partha Niyogi |
| 2006 | Higher Lower Bounds for Near-Neighbor and Further Rich Problems. Mihai Patrascu, Mikkel Thorup |
| 2006 | How to Play Unique Games Using Embeddings. Eden Chlamtac, Konstantin Makarychev, Yury Makarychev |
| 2006 | Improved Approximation Algorithms for Large Matrices via Random Projections. Tamás Sarlós |
| 2006 | Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. Niv Buchbinder, Joseph Naor |
| 2006 | Improved Dynamic Planar Point Location. Lars Arge, Gerth Stølting Brodal, Loukas Georgiadis |
| 2006 | Improved approximation algorithms for multidimensional bin packing problems. Nikhil Bansal, Alberto Caprara, Maxim Sviridenko |
| 2006 | Inclusion--Exclusion Algorithms for Counting Set Partitions. Andreas Björklund, Thore Husfeldt |
| 2006 | Index Coding with Side Information. Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, Tomer Kol |
| 2006 | Input-Indistinguishable Computation. Silvio Micali, Rafael Pass, Alon Rosen |
| 2006 | Local Graph Partitioning using PageRank Vectors. Reid Andersen, Fan R. K. Chung, Kevin J. Lang |
| 2006 | Lower Bounds for Additive Spanners, Emulators, and More. David P. Woodruff |
| 2006 | Lower bounds for circuits with MOD_m gates. Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien |
| 2006 | Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. James R. Lee, Assaf Naor |
| 2006 | Minimum Bounded Degree Spanning Trees. Michel X. Goemans |
| 2006 | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Alexandr Andoni, Piotr Indyk |
| 2006 | New Limits on Fault-Tolerant Quantum Computation. Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger |
| 2006 | New Results for Learning Noisy Parities and Halfspaces. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami |
| 2006 | Norm of the inverse of a random matrix. Mark Rudelson |
| 2006 | On a Geometric Generalization of the Upper Bound Theorem. Uli Wagner |
| 2006 | On the Compressibility of NP Instances and Cryptographic Applications. Danny Harnik, Moni Naor |
| 2006 | On the Impact of Combinatorial Structure on Congestion Games. Heiner Ackermann, Heiko Röglin, Berthold Vöcking |
| 2006 | On the Optimality of the Dimensionality Reduction Method. Alexandr Andoni, Piotr Indyk, Mihai Patrascu |
| 2006 | On the Quantum Query Complexity of Local Search in Two and Three Dimensions. Xiaoming Sun, Andrew Chi-Chih Yao |
| 2006 | On the time complexity of 2-tag systems and small universal Turing machines. Damien Woods, Turlough Neary |
| 2006 | Planar Earthmover is not in L_1. Assaf Naor, Gideon Schechtman |
| 2006 | Planar Point Location in Sublogarithmic Time. Mihai Patrascu |
| 2006 | Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. Timothy M. Chan |
| 2006 | Points on Computable Curves. Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo |
| 2006 | Postselection threshold against biased noise. Ben Reichardt |
| 2006 | Ramsey partitions and proximity data structures. Manor Mendel, Assaf Naor |
| 2006 | SDP gaps and UGC-hardness for MAXCUTGAIN. Subhash Khot, Ryan O'Donnell |
| 2006 | Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, Adam D. Smith |
| 2006 | Settling the Complexity of Two-Player Nash Equilibrium. Xi Chen, Xiaotie Deng |
| 2006 | Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources. Nadine Baumann, Martin Skutella |
| 2006 | Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan |
| 2006 | Strategic Network Formation through Peering and Service Agreements. Elliot Anshelevich, F. Bruce Shepherd, Gordon T. Wilfong |
| 2006 | Subspace Polynomials and List Decoding of Reed-Solomon Codes. Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan |
| 2006 | Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. Yael Tauman Kalai, Ran Raz |
| 2006 | The Effectiveness of Lloyd-Type Methods for the k-Means Problem. Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy |
| 2006 | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. Christian Borgs, Jennifer T. Chayes, Elchanan Mossel, Sébastien Roch |
| 2006 | Towards Secure and Scalable Computation in Peer-to-Peer Networks. Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2006 | Witnesses for non-satisfiability of dense random 3CNF formulas. Uriel Feige, Jeong Han Kim, Eran Ofek |
| 2006 | Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method. David Arthur, Sergei Vassilvitskii |