Accepted papers for FOCS '99

Lovasz's Lemma for the K-Level of Concave Surfaces and its Applications
Naoki Katoh and Takeshi Tokuyama

A Non-linear Time Lower Bound for Boolean Branching Programs
Miklos Ajtai

Efficient testing of large graphs
Noga Alon and Eldar Fischer and Michael Krivelevich and Mario Szegedy

Setting Parameters by Example
David Eppstein

Lower Bounds for the Rank of Matrix Multiplication
Markus Blaeser

Reducing Randomness via Chinese Remaindering
Manindra Agrawal and Somenath Biswas

A probabilistic algorithm for k-SAT and constraint satisfaction problems
Uwe Sch"oning

Derandomizing Arthur-Merlin Games using Hitting Sets
Peter Bro Miltersen and N.V. Vinodchandran

A near-tight lower bound on the time complexity of distributed MST construction
D. Peleg and V. Rubinovich

A Study of Proof Search Algorithms for Resolution etc
Maria Bonet and Nicola Galesi

PSPACE has constant-round quantum interactive proof systems
John Watrous 

Improved Bounds for Sampling Colorings
Eric Vigoda

Random CNF's are Hard for the Polynomial Calculus
Eli Ben-Sasson and Russell Impagliazzo

Noncryptographic Selection Protocols
Uriel Feige

Cuts, Trees and l_1-Embeddings of Graphs
Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair

Finding Double Euler Trails of Planar Graphs in Linear Time
Zhi-Zhong Chen and Xin He and Chun-Hsi Huang

Approximation Schemes for Scheduling to Minimize Average Weighted Completion
Time with Release Dates
C. Chekuri and D. Karger and S. Khanna and M. Skutella and C. Stein
F. Afrati and E. Bampis and C. Kenyon and I. Milis

Reducing Network Congestion and Blocking Probability Through Balanced Allocation
Malwina L. Luczak and Eli Upfal

All Pairs Shortest Paths in Undirected Graphs with Integer Weights
Avi Shoshan and Uri Zwick

Dynamic planar convex hull operations in near-logarithmic amortized time
Timothy M. Chan

Approximating fractional multicommodity flow independent of the number of commodities
Lisa K. Fleischer

Limits on the Efficiency of One-Way Permutation-Based Hash Functions
Jeong Han Kim and Daniel R. Simon and Prasad Tetali

Cache-Oblivious Algorithms
Matteo Frigo and Charles E. Leiserson and Harald Prokop and Sridhar Ramachandran

Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields
Jon Kleinberg and Eva Tardos

Near-Optimal conversion of Hardness into Pseudo-Randomness 
Russell Impagliazzo and Ronen Shaltiel and Avi Wigderson 

Taking a walk in a planar arrangement
Sariel Har-Peled

Markovian Coupling is not powerful as Conductance
V.S. Anil Kumar  and  H.  Ramesh

Fairness in Routing and Load Balancing
Jon Kleinberg and Yuval Rabani and Eva Tardos

Algorithmic theories of learning
Rosa I. Arriaga and Santosh Vempala

Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs
Valerie King

On counting independent sets in sparse graphs
Martin Dyer and Alan Frieze and Mark Jerrum

How Asymmetry Helps Load Balancing
B. Voecking

A Theoretical Framework for Memory-Adaptive Algorithms
Rakesh D. Barve and Jeffrey Scott Vitter

Learning mixtures of Gaussians
Sanjoy Dasgupta

Non-Malleable Non-Interactive Zero Knowledge and Achieving Chosen-Ciphertext Security
Amit Sahai

Boosting and Hardness Amplification
Adam R. Klivans and Rocco A. Servedio

The Directed Steiner Network problem is tractable for a constant number of terminals
Jon Feldman and Matthias Ruhl

Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems
Kamal Jain and Vijay V. Vazirani

Random walks on truncated cubes and sampling 0-1 knapsack solutions
Ben Morris and Alistair Sinclair

Hardness of Approximating Sigma_2^p Minimization Problems
Christopher Umans

On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis
P. Oscar Boykin and Tal Mor and Mathew Pulver and Vwani Roychowdhury and Farrokh Vatan

Edge-Disjoint Routing in Plane Switch Graphs in Linear Time
Karsten Weihe

Optimal lower bounds for quantum automata and random access codes
Ashwin Nayak

Finding Maximal Repetitions in a Word in Linear Time
Kolpakov, Roman and Kucherov, Gregory

Reducing Error Probability in Quantum Algorithms
H. Buhrman and R. Cleve and R. de Wolf and Ch. Zalka

Satisfiability of Word Equations with Constants is in PSPACE
Wojciech Plandowski

Hardness of Approximating the Minimum Distance of a Linear Code
Ilya Dumer and Daniele Micciancio and Madhu Sudan

Verifiable Random Functions
Silvio Micali and Michael Rabin and Salil Vadhan

Error Reduction for Extractors
Ran Raz and Omer Reingold and Salil Vadhan

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings
Martin Farach-Colton and Piotr Indyk

Scheduling to Minimize Average Stretch 
Johannes E. Gehrke and S. Muthukrishnan and Rajmohan Rajaraman and Anthony Shaheen

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics
Christian Borgs and Jennifer Chayes and Alan Frieze and Jeong Han Kim and Prasad Tetali and Eric Vigoda and Van Ha Vu

On the Complexity of SAT
Richard J Lipton and Anastasios Viglas

An Approximate L1-Difference Algorithm for Massive Data Streams
J. Feigenbaum and S. Kannan and M. Strauss and M. Viswanathan

Long-Lived and Adaptive Collect with Applications
Y. Afek and G. Stupp and D. Touitou

A better lower bound for quantum algorithms searching an ordered list
Andris Ambainis

Finely-competitive paging
Avrim Blum and Carl Burch and Adam Kalai

On quantum and classical space-bounded processes with algebraic transition amplitudes
John Watrous

Non-Interactive CryptoComputing For NC1
Tomas Sander and Adam Young and Moti Yung

Stochastic Load Balancing and Related Problems
Ashish Goel and Piotr Indyk

Improved Combinatorial Algorithms for the Facility Location and k-Median Problems
Moses Charikar and Sudipto Guha

Magic Functions
Dwork and Naor and Reingold and Stockmeyer

Algorithmic Aspects of Protein Structure Similarity
Deborah Goldman and Sorin Istrail and Christos H. Papadimitriou

Weak adversaries for the k-server problem
Elias Koutsoupias

A PTAS for Clustering in Metric Spaces
Piotr Indyk

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems 
Arnon Amir and Alon Efrat and Piotr Indyk and Hanan Samet 

Regular Languages Are Testable With a Constant Number of Queries
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy