47th Annual IEEE Foundations of Computer Science

Berkeley, CA Oct 21—24, 2006

IEEE Computer Society.





Session 1A

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

  Minh-Huyen Nguyen, Shien Jin Ong, and Salil Vadhan


Fault-Tolerant Distributed Computing in Full-Information Networks

  Shafi Goldwasser, Elan Pavlov and Vinod Vaikuntanathan


Explicit Exclusive Set Systems with Cryptographic Applications  [presentation]

  Craig Gentry, Zulfikar Ramzan, and David P. Woodruff



Session 2A

A local switch markov chain on given degree graphs with
application in connectivity of peer-to-peer networks

  Tomas Feder, Adam Guetz, Milena Mihail and Amin Saberi


Local Peering and Service Contracts in Strategic Network Formation

  Elliot Anshelevich, Bruce Shepherd and Gordon Wilfong


Towards Secure and Scalable Computation in Peer-to-Peer Networks

  Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee



Session 1B

A simple condition implying rapid mixing of single-site dynamics on spin systems

  Thomas P. Hayes


Heat flow and a faster algorithm to compute the surface area of a convex body [presentation]

  Mikhail Belkin, Hariharan Narayanan and Partha Niyogi


Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization

  Laszlo Lovasz and Santosh Vempala



Session 2B

L_p metrics on the Heisenberg group and the Goemans-Linial conjecture

  James R. Lee and Assaf Naor


Ramsey partitions and proximity data structures

  Manor Mendel. Assaf Naor



Algorithms on negatively curved spaces

  Robert Krauthgamer and James R. Lee










Session 3, Invited Talk:
Theory of Computation as a Lens on the Sciences: The Example of Computational Molecular Biology 
  Richard Karp, UC Berkeley.

Session 4A


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

  Roman Vershynin


Improved Approximation Algorithms for Large Matrices via Random Projections


  Tamás Sarlós


Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method

  David Arthur and Sergei Vassilvitskii


The Effectiveness of Lloyd-type Methods for the k-Means Problem

  Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy



Session 5A: 4:05-4:50

Chair: Moses Charikar


SDP gaps and UGC-hardness for MaxCutGain

  Subhash Khot and Ryan O'Donnell



Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets

  Venkatesan Guruswami and Anindya Patthak



Session 4B


Better lossless condensers through derandomized curve samplers

  Amnon Ta-Shma and Christopher Umans


List-decoding direct product codes and uniform hardness amplification

  Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets


Index Coding with Side Information

  Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram and Tomer Kol


Subspace Polynomials and List Decoding of Reed-Solomon Codes

  Eli Ben-Sasson, Swastik Kopparty and Jaikumar Radhakrishnan




Session 5B: 4:05-4:50

Chair: Ashwin Nayak


Cryptography from Anonymity

  Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai


Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

  Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith



Session 6, Best Paper Award:

Settling the Complexity of 2-Player Nash-Equilibrium

  Xi Chen and Xiaotie Deng



Session 7A

Minimum Bounded Degree Spanning Trees

  Michel Goemans


Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs

  Tamas Kiraly and Lap Chi Lau


Improved Bounds for Online Routing and Packing via a Primal-Dual Approach

  Niv Buchbinder and Seffi Naor












Session 8A

Concurrent Non-Malleable Zero Knowledge

  Boaz Barak, Manoj Prabhakaran and Amit Sahai


Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP

  Yael Tauman Kalai and Ran Raz


Input-Indistinguishable Computation

  Silvio Micali, Rafael Pass and Alon Rosen


Session 7B

Improved Dynamic Planar Point Location

  Lars Arge, Gerth Stolting Brodal and Loukas Georgiadis


Coresets for Weighted Facilities and Their Applications

  Dan Feldman, Amos Fiat, and Micha Sharir



Planar Point Location in Sublogarithmic Time

  Mihai Patrascu


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



Session 8B

Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders

  Krzysztof Onak and Pawel Parys


Lower Bounds for Additive Spanners, Emulators, and More [presentation]

  David P. Woodruff


Solving Evacuation Problems Efficiently - Earliest Arrival Flows with Multiple Sources

  Nadine Baumann and Martin Skutella


Session 9, Invited Talk:

A critique of pure vision

  Terry Sejnowski, Salk Institute


Session 10A

New limits on fault-tolerant quantum computation

  Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver and Falk Unger


Postselection threshold against biased noise

  Ben W. Reichardt



On the Quantum Query Complexity of Local Search in Two and Three Dimensions

  Xiaoming Sun and Andrew C. Yao


On the time complexity of 2-tag systems and small universal Turing machines

  Damien Woods, Turlough Neary







Session 11A

Norm of the inverse of a random matrix

  Mark Rudelson


Witnesses for non-satisfiability of dense random 3CNF formulas

  Uriel Feige, Jeong Han Kim and Eran Ofek


Session 10B

On the Optimality of the Dimensionality Reduction Method

  Alexandr Andoni, Piotr Indyk and Mihai Patrascu



Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

  Alexandr Andoni and Piotr Indyk


Points on Computable Curves

  Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo



Local Graph Partitioning using PageRank Vectors

  Reid Andersen, Fan Chung and Kevin Lang




Session 11B: 4:05-4:50

Accidental Algorithms

  Leslie Valiant


The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

  Christian Borgs, Jennifer Chayes, Elchanan Mossel, and Sebastien Roch


Session 12, Machtey Award for Best Student Paper:

Algebraic Structures and Algorithms for Matching and Matroid Problems [presentation]

  Nicholas J. A. Harvey





Session 13A

Hardness of Learning Halfspaces with Noise

  Venkatesan Guruswami and Prasad Raghavendra


Cryptographic Hardness Results for Learning Intersections of Halfspaces

  Adam R. Klivans and Alexander A. Sherstov


New Results for Learning Noisy Parities and Halfspaces

  Vitaly Feldman, Parikshit Gopalan, Subhash Khot and Ashok Kumar Ponnuswami



Session 14A

Computing Nash Equilibria: Approximation and Smoothed Complexity

  Xi Chen, Xiaotie Deng and Shang-Hua Teng


On the Impact of Combinatorial Structure on Congestion Games

  Heiner Ackermann, Heiko Roeglin and Berthold Voecking


Balanced Allocations of Cake

  Jeff Edmonds and Kirk Pruhs


Session 13B

Inclusion-Exclusion Algorithms for Counting Set Partitions [presentation (movie)]

  Andreas Björklund and Thore Husfeldt


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

  Mikko Koivisto


Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

  Surender Baswana and Telikepalli Kavitha





Session 14B

A Geometric Generalization of the Upper Bound Theorem

  Uli Wagner



Higher Lower Bounds for Near-Neighbor and Further Rich Problems

  Mihai Patrascu and Mikkel Thorup


Planar Earthmover is not in L_1

  Assaf Naor and Gideon Schechtman


Session 15, Invited Talk:

The Emerging Intersection of Social and Technological Networks: Open Questions and Algorithmic Challenges

  Jon Kleinberg, Cornell



Session 16A

Approximation algorithms for allocation problems: Improving the factor of 1-1/e

  Uriel Feige, Jan Vondrak


Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems

  Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour


How to Play Unique Games Using Embeddings

  Eden Chlamtac and Konstantin Makarychev and Yury Makarychev


Improved approximation algorithms for multidimensional bin packing problems

  Nikhil Bansal, Alberto Caprara and Maxim Sviridenko



Session 16B

Lower bounds for circuits with MOD_m gates

  Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlak and Denis Therien

On the Compressibility of NP Instances and Cryptographic Applications [presentation]

  Danny Harnik and Moni Naor



Dispersion of Mass and the Complexity of Randomized Algorithms

  Luis Rademacher and Santosh Vempala


An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

  Alexander A. Razborov and Sergey Yekhanin


For updates, corrections or comments please email focsinformal@gmail.com.