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

[presentation]

  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

AND

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

 

 


 

TUESDAY, Oct 24
 

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.