List of accepted papers for FOCS 2006:


Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. 

Shafi Goldwasser, Elan Pavlov, Vinod Vaikuntanathan: 
Fault-Tolerant Distributed Computing in Full-Information Networks. 

Craig Gentry, Zulfikar Ramzan, David P. Woodruff: 
Explicit Exclusive Set Systems with Applications to Broadcast Encryption. 

Thomas P. Hayes: 
A simple condition implying rapid mixing of single-site dynamics on spin systems. 

Mikhail Belkin, Hariharan Narayanan, Partha Niyogi: 
Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. 

László Lovász, Santosh Vempala: 
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. 

Tomás Feder, Adam Guetz, Milena Mihail, Amin Saberi: 
A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. 

Elliot Anshelevich, Bruce Shepherd, Gordon T. Wilfong: 
Strategic Network Formation through Peering and Service Agreements. 

Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee: 
Towards Secure and Scalable Computation in Peer-to-Peer Networks. 

James R. Lee, Assaf Naor: 
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. 

Manor Mendel, Assaf Naor: 
Ramsey partitions and proximity data structures. 

Robert Krauthgamer, James R. Lee: 
Algorithms on negatively curved spaces. 

Roman Vershynin: 
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. 

Tamás Sarlós: 
Improved Approximation Algorithms for Large Matrices via Random Projections. 

David Arthur, Sergei Vassilvitskii: 
Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method. 

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: 
The Effectiveness of Lloyd-Type Methods for the k-Means Problem. 

Amnon Ta-Shma, Christopher Umans: 
Better lossless condensers through derandomized curve samplers. 

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: 
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. 

Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, Tomer Kol: 
Index Coding with Side Information.

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: 
Subspace Polynomials and List Decoding of Reed-Solomon Codes. 

Subhash Khot, Ryan O'Donnell: 
SDP gaps and UGC-hardness for MAXCUTGAIN. 

Venkatesan Guruswami, Anindya C. Patthak: 
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. 

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: 
Cryptography from Anonymity. 

Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, Adam Smith: 
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. 

Xi Chen, Xiaotie Deng: 
Settling the Complexity of Two-Player Nash Equilibrium. 

Michel X. Goemans: 
Minimum Bounded Degree Spanning Trees. 

Tamás Király, Lap Chi Lau: 
Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. 

Niv Buchbinder, Joseph Naor: 
Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. 

Lars Arge, Gerth Střlting Brodal, Loukas Georgiadis: 
Improved Dynamic Planar Point Location. 

Dan Feldman, Amos Fiat, Micha Sharir: 
Coresets forWeighted Facilities and Their Applications. 

Mihai Patrascu: 
Planar Point Location in Sublogarithmic Time. 

Timothy M. Chan: 
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry.

Boaz Barak, Manoj Prabhakaran, Amit Sahai: 
Concurrent Non-Malleable Zero Knowledge. 

Yael Tauman Kalai, Ran Raz: 
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. 

Silvio Micali, Rafael Pass, Alon Rosen: 
Input-Indistinguishable Computation. 

Krzysztof Onak, Pawel Parys: 
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. 

David P. Woodruff: 
Lower Bounds for Additive Spanners, Emulators, and More. 

Nadine Baumann, Martin Skutella: 
Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources. 

Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger: 
New Limits on Fault-Tolerant Quantum Computation.

Ben Reichardt: 
Postselection threshold against biased noise. 

Xiaoming Sun, Andrew Chi-Chih Yao: 
On the Quantum Query Complexity of Local Search in Two and Three Dimensions. 

Damien Woods, Turlough Neary: 
On the time complexity of 2-tag systems and small universal Turing machines.

Alexandr Andoni, Piotr Indyk, Mihai Patrascu: 
On the Optimality of the Dimensionality Reduction Method. 

Alexandr Andoni, Piotr Indyk: 
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. 

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo: 
Points on Computable Curves. 

Reid Andersen, Fan R. K. Chung, Kevin Lang: 
Local Graph Partitioning using PageRank Vectors. 

Mark Rudelson: 
Norm of the inverse of a random matrix.

Uriel Feige, Jeong Han Kim, Eran Ofek: 
Witnesses for non-satisfiability of dense random 3CNF formulas. 

Leslie G. Valiant: 
Accidental Algorthims. 

Christian Borgs, Jennifer T. Chayes, Elchanan Mossel, Sébastien Roch: 
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. 

Nicholas J. A. Harvey: 
Algebraic Structures and Algorithms for Matching and Matroid Problems. 

Venkatesan Guruswami, Prasad Raghavendra: 
Hardness of Learning Halfspaces with Noise. 

Adam R. Klivans, Alexander A. Sherstov: 
Cryptographic Hardness for Learning Intersections of Halfspaces. 

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: 
New Results for Learning Noisy Parities and Halfspaces. 

Andreas Björklund, Thore Husfeldt: 
Inclusion--Exclusion Algorithms for Counting Set Partitions. 

Mikko Koivisto: 
An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion. 

Surender Baswana, Telikepalli Kavitha: 
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths. 

Xi Chen, Xiaotie Deng, Shang-Hua Teng: 
Computing Nash Equilibria: Approximation and Smoothed Complexity. 

Heiner Ackermann, Heiko Röglin, Berthold Vöcking: 
On the Impact of Combinatorial Structure on Congestion Games. 

Jeff Edmonds, Kirk Pruhs: 
Balanced Allocations of Cake. 

Uli Wagner: 
On a Geometric Generalization of the Upper Bound Theorem. 

Mihai Patrascu, Mikkel Thorup: 
Higher Lower Bounds for Near-Neighbor and Further Rich Problems. 

Assaf Naor, Gideon Schechtman: 
Planar Earthmover is not in L_1. 

Uriel Feige, Jan Vondrák: 
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. 

Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: 
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. 

Eden Chlamtac, Konstantin Makarychev, Yury Makarychev: 
How to Play Unique Games Using Embeddings. 

Nikhil Bansal, Alberto Caprara, Maxim Sviridenko: 
Improved approximation algorithms for multidimensional bin packing problems. 

Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien: 
Lower bounds for circuits with MOD_m gates. 

Danny Harnik, Moni Naor: 
On the Compressibility of NP Instances and Cryptographic Applications. 

Luis Rademacher, Santosh Vempala: 
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. 

Alexander A. Razborov, Sergey Yekhanin: 
An Omega(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval.