Papers accepted to FOCS '00

Fourier Sampling Arbitrary Periodic Functions
Lisa Hales

Testing of Clustering
Noga Alon and Seannie Dar and Michal Parnas and Dana Ron

A Polylogarithmic Approximation of the Minimum Bisection
Uriel Feige and Robert Krauthgamer 

Topological Persistence and Simplification
Herbert Edelsbrunner and David Letscher and Afra Zomorodian

Testing of Functions that have small width Branching Programs 
Ilan Newman

On the Existence of Booster Types
Maurice Herlihy and Eric Ruppert

Fully Dynamic Transitive Closure: Breaking Through the O(n^2) Barrier
Camil Demetrescu and Giuseppe F. Italiano

The Online Median Problem
Ramgopal Mettu and Greg Plaxton

Using upper confidence bounds for online learning
Peter Auer

Universality and Tolerance
N. Alon and M. Capalbo and Y. Kohayakawa and V. Rodl and A. Rucinski and E. Szemeredi 

Succinct quantum proofs for properties of finite groups
John Watrous

Detecting a Network Failure
Jon Kleinberg 

Super-linear time-space tradeoff lower bounds for randomized computation
Paul Beame and Mike Saks and Xiaodong Sun and Erik Vee

Makespan Minimization in No-Wait Flow Shops: a Polynomial Time Approximation Scheme
Maxim Sviridenko 

On the boundary complexity of the union of fat triangles
Janos Pach and Gabor Tardos

Extracting Randomness via Repeated Condensing
Omer Reingold and Ronen Shaltiel and Avi Wigderson

Linear Waste of Best Fit Bin Packing on Skewed Distributions
Claire Kenyon and Michael Mitzenmacher

A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning 
Ileana Streinu

On Levels in Arrangements of Curves
Timothy M. Chan

How bad is selfish routing?
Tim Roughgarden and Eva Tardos

Approximating the single source unsplittable min-cost flow problem
Martin Skutella

Pseudorandom Generators in Propositional Proof Complexity
Michael Alekhnovich and Eli Ben-Sasson and Alexander A. Razborov and Avi Wigderson

Private Quantum Channels
Andris Ambainis and Michele Mosca and Alain Tapp and Ronald de Wolf

Building Steiner Trees with Incomplete Global Knowledge
David R. Karger and Maria Minkoff

The common fragment of CTL and LTL
Monika Maidl

Opportunistic Data Structures with Applications
Paolo Ferragina and Giovanni Manzini

Extracting Randomness from Samplable Distributions
Luca Trevisan and Salil Vadhan

Hardness of Approximate Hypergraph Coloring
Venkatesan Guruswami and Johan Hastad and Madhu Sudan

"Soft-decision" Decoding of Chinese Remainder Codes
Venkatesan Guruswami and Amit Sahai and Madhu Sudan

Cache-Oblivious B-Trees
Michael A. Bender and Erik D. Demaine and Martin Farach-Colton

Clustering Data Streams
Sudipto Guha and Nina Mishra and Rajeev Motwani and Liadan O'Callaghan

The Randomness Recycler:  A New Technique for Perfect Sampling
James A. Fill and Mark L. Huber

Cost-Distance: Two metric network design
Adam Meyerson and Kamesh Munagala and Serge Plotkin

On the Hardness of Graph Isomorphism
Jacobo Toran

Using Expander Graphs to Find Vertex Connectivity
Harold N. Gabow

Fairness Measures for Resource Allocation
Amit Kumar and Jon Kleinberg

Zaps and their applications
Cynthia Dwork and Moni Naor

Randomized Rumor Spreading
Richard Karp and Christian Schindelhauer and Scott Shenker and Berthold Vocking

Nested Graph Dissection and Approximation Algorithms
Sudipto Guha

Hierarchical Placement and Network Design Problems.
Sudipto Guha and Adam Meyerson and Kamesh Munagala

New Data Structures for Orthogonal Range Searching
Stephen Alstrup and Gerth S. Brodal and Theis Rauhe

Existential Second-Order Logic over Graphs: Charting the Tractability Frontier 
Georg Gottlob and Phokion Kolatis and Thomas Schwentick

Fast broadcasting and gossiping in radio networks
M. Chrobak and L. Gasieniec and W. Rytter

The Quantum Complexity of Set Membership
Jaikumar Radhakrishnan and Pranab Sen and S. Venkatesh

Lower bounds on the efficiency of generic cryptographic constructions
Rosario Gennaro and Luca Trevisan

The product replacement algorithm is polynomial
Igor Pak

Concurrent Oblivious Transfer
Juan Garay and Phil MacKenzie

Straighting Polygonal Arcs and Convexifying Polygonal Cycles
Robert Connelly and Erik D. Demaine and Guenter Rote

Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation
Piotr Indyk

Testing that Distributions Are Close
Tugkan Batu and Lance Fortnow and Ronitt Rubinfeld and Warren D. Smith and Patrick White

Efficient Algorithms for Universal Portfolios
Adam Kalai and Santosh Vempala

Random graph models for the Web graph
Ravi Kumar and Prabhakar Raghavan and Sridhar Rajagopalan and D Sivakumar and Andrew Tomkins and Eli Upfal

Combinatorial feature selection problems
Moses Charikar and Venkatesan Guruswami and Ravi Kumar and Sridhar Rajagopalan and Amit Sahai

On the Approximability of Trade-offs and Optimal Access of Web Sources
Christos H. Papadimitriou and Mihalis Yannakakis

Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation 
Yuval Ishai and Eyal Kushilevitz

The cover time, the blanket time, and the Matthews bound
J. Kahn and J.H. Kim and L. Lovasz and V. H. Vu

Fast parallel circuits for the quantum Fourier transform
Richard Cleve and John Watrous

Polynomial Time Approximation Schemes for Geometric $k$-Clustering
Rafail Ostrovsky and Yuval Rabani 

Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Omer Reingold and Salil Vadhan and Avi Wigderson

Optimization Problems in Congestion Control
R. Karp and E. Koutsoupias and C. Papadimitriou and S. Shenker

The Relationship between Public Key Encryption and Oblivious Transfer.
Yeal Gertner and Sampath Kannan and Tal Malkin and Omer Reingold and Mahesh Viswanathan

Computing the Determinant and Smith Form of an Integer Matrix
W. Eberly and M. Giesbrecht and G. Villard

Nearly Optimal Expected-Case Planar Point Location
S. Arya and T. Malamatos and D. M. Mount

Optimal policies for greedy 3-SAT algorithms
Dimitris Achlioptas and Gregory B. Sorkin

Sampling adsorbing staircase walks using a new Markov chain decomposition method
Russell Martin and Dana Randall

On clusterings: good, bad and spectral
Santosh Vempala and Adrian Vetta and Ravi Kannan