Accepted Papers
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)

L_p metrics on the Heisenberg group and the Goemans-Linial conjecture
by James R. Lee and Assaf Naor

A Geometric Generalization of the Upper Bound Theorem
by Uli Wagner

A generalization of the Dobrushin uniqueness condition and applications to MCMC sampling
by Thomas P. Hayes

A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks
by Tomas Feder, Adam Guetz, Milena Mihail and Amin Saberi

Accidental Algorithms
by Leslie Valiant

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

Algorithms on negatively curved spaces
by Robert Krauthgamer and James R. Lee

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

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval
by A.A. Razborov, S. Yekhanin

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

Approximation algorithms for allocation problems: Improving the factor of 1-1/e
by Uriel Feige, Jan Vondrak

Balanced Allocations of Cake
by Jeff Edmonds and Kirk Pruhs

Better lossless condensers through derandomized curve samplers
by Amnon Ta-Shma and Christopher Umans

Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method
by Roman Vershynin

Bounded Degree Minimum Spanning Trees
by Michel Goemans

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

Concurrent Non-Malleable Zero Knowledge
by Boaz Barak, Manoj Prabhakaran and Amit Sahai

Coresets for Weighted Facilities and Their Applications
by Dan Feldman, Amos Fiat, and Micha Sharir

Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets
by Venkatesan Guruswami and Anindya Patthak

Cryptographic Hardness Results for Learning Intersections of Halfspaces
by Adam R. Klivans and Alexander A. Sherstov

Cryptography from Anonymity
by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai

Dispersion of Mass and the Complexity of Randomized Algorithms
by Luis Rademacher and Santosh Vempala

Explicit Exclusive Set Systems with Cryptographic Applications
by Craig Gentry, Zulfikar Ramzan, and David P. Woodruff

Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization
by Laszlo Lovasz and Santosh Vempala

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

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

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

Hardness of Learning Halfspaces with Noise
by Venkatesan Guruswami and Prasad Raghavendra

Heat flow and a faster algorithm to compute the surface area of a convex body
by Mikhail Belkin and Hariharan Narayanan and Partha Niyogi

Higher Lower Bounds for Near-Neighbor and Further Rich Problems
by Mihai Patrascu and Mikkel Thorup

How to Play any Unique Game
by Eden Chlamtac and Konstantin Makarychev and Yury Makarychev

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

Improved Bounds for Online Routing and Packing via a Primal-Dual Approach
by Niv Buchbinder and Seffi Naor

Improved Dynamic Planar Point Location
by Lars Arge and Gerth Stolting Brodal and Loukas Georgiadis

Improved approximation algorithms for multidimensional bin packing problems
by Nikhil Bansal and Alberto Caprara and Maxim Sviridenko

Inclusion-Exclusion Algorithms for Counting Set Partitions
by Andreas Björklund and Thore Husfeldt

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

Input-Indistinguishable Computation
by Silvio Micali, Rafael Pass and Alon Rosen

List-decoding direct product codes and uniform hardness amplification
by Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets

Local Graph Partitioning using PageRank Vectors
by Reid Andersen, Fan Chung and Kevin Lang

Local Peering and Service Contracts in Strategic Network Formation
by Elliot Anshelevich, Bruce Shepherd and Gordon Wilfong

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

Lower bounds for circuits with MOD_m gates
by Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlak and Denis Therien

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
by Alexandr Andoni and Piotr Indyk

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

New limits on fault-tolerant quantum computation
by Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver and Falk Unger

Norm of the inverse of a random matrix
by Mark Rudelson

On the Compressibility of NP Instances and Cryptographic Applications
by Danny Harnik and Moni Naor

On the Impact of Combinatorial Structure on Congestion Games
by Heiner Ackermann, Heiko Roeglin and Berthold Voecking

On the Optimality of the Dimensionality Reduction Method
by Alexandr Andoni, Piotr Indyk and Mihai Patrascu

On the Quantum Query Complexity of Local Search in Two and Three Dimensions
by Xiaoming Sun and Andrew C. Yao

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

Planar Earthmover is not in L_1
by Assaf Naor and Gideon Schechtman

Planar Point Location in Sublogarithmic Time
by Mihai Patrascu

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

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

Postselection threshold against biased noise
by Ben W. Reichardt

Ramsey partitions and proximity data structures
by Manor Mendel. Assaf Naor

SDP gaps and UGC-hardness for MaxCutGain
by Subhash Khot and Ryan O'Donnell

Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
by Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith

Settling the Complexity of 2-Player Nash-Equilibrium
by Xi Chen and Xiaotie Deng

Solving Evacuation Problems Efficiently - Earliest Arrival Flows with Multiple Sources
by Nadine Baumann and Martin Skutella

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

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

Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP
by Yael Tauman Kalai and Ran Raz

The Effectiveness of Lloyd-type Methods for the k-Means Problem
by Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy

The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
by Christian Borgs, Jennifer Chayes, Elchanan Mossel, and Sebastien Roch

Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs
by Tamas Kiraly and Lap Chi Lau

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

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

Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method.
by David Arthur and Sergei Vassilvitskii