40. FOCS 1999: New York, NY, USA

40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA. IEEE Computer Society, 1999

Session 1

Kamal Jain, Vijay V. Vazirani:
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. 2-13
Electronic Edition (IEEE Computer Society DL) BibTeX
Jon M. Kleinberg, Éva Tardos:
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. 14-23
Electronic Edition (IEEE Computer Society DL) BibTeX
Lisa Fleischer:
Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. 24-31
Electronic Edition (IEEE Computer Society DL) BibTeX
Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko:
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. 32-44
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2

Markus Bläser:
A 5/2 n²-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields. 45-50
Electronic Edition (IEEE Computer Society DL) BibTeX
Eric Vigoda:
Improved Bounds for Sampling Colorings. 51-59
Electronic Edition (IEEE Computer Society DL) BibTeX
Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. 60-70
Electronic Edition (IEEE Computer Society DL) BibTeX
Peter Bro Miltersen, N. V. Vinodchandran:
Derandomizing Arthur-Merlin Games Using Hitting Sets. 71-80
Electronic Edition (IEEE Computer Society DL) BibTeX
Valerie King:
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. 81-91
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3

Timothy M. Chan:
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. 92-99
Electronic Edition (IEEE Computer Society DL) BibTeX
Sariel Har-Peled:
Taking a Walk in a Planar Arrangement. 100-111
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4

John Watrous:
PSPACE Has Constant-Round Quantum Interactive Proof Systems. 112-119
Electronic Edition (IEEE Computer Society DL) BibTeX
Silvio Micali, Michael O. Rabin, Salil P. Vadhan:
Verifiable Random Functions. 120-130
Electronic Edition (IEEE Computer Society DL) BibTeX
Berthold Vöcking:
How Asymmetry Helps Load Balancing. 131-141
Electronic Edition (IEEE Computer Society DL) BibTeX
Uriel Feige:
Noncryptographic Selection Protocols. 142-153
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5A

Piotr Indyk:
A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. 154-159
Electronic Edition (IEEE Computer Society DL) BibTeX
Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet:
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. 160-170
Electronic Edition (IEEE Computer Society DL) BibTeX
Martin Farach-Colton, Piotr Indyk:
Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. 171-180
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5B

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Near-Optimal Conversion of Hardness into Pseudo-Randomness. 181-190
Electronic Edition (IEEE Computer Society DL) BibTeX
Ran Raz, Omer Reingold, Salil P. Vadhan:
Error Reduction for Extractors. 191-201
Electronic Edition (IEEE Computer Society DL) BibTeX
Manindra Agrawal, Somenath Biswas:
Primality and Identity Testing via Chinese Remaindering. 202-209
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6A

Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
On Counting Independent Sets in Sparse Graphs. 210-217
Electronic Edition (IEEE Computer Society DL) BibTeX
Christian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu:
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. 218-229
Electronic Edition (IEEE Computer Society DL) BibTeX
Ben Morris, Alistair Sinclair:
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. 230-240
Electronic Edition (IEEE Computer Society DL) BibTeX
V. S. Anil Kumar, H. Ramesh:
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain. 241-252
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6B

David Peleg, Vitaly Rubinovich:
A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. 253-261
Electronic Edition (IEEE Computer Society DL) BibTeX
Yehuda Afek, Gideon Stupp, Dan Touitou:
ong-lived Adaptive Collect with Applications. 262-272
Electronic Edition (IEEE Computer Society DL) BibTeX
Rakesh D. Barve, Jeffrey Scott Vitter:
A Theoretical Framework for Memory-Adaptive Algorithms. 273-284
Electronic Edition (IEEE Computer Society DL) BibTeX
Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran:
Cache-Oblivious Algorithms. 285-298
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7A

Jon Feldman, Matthias Ruhl:
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. 299-308
Electronic Edition (IEEE Computer Society DL) BibTeX
David Eppstein:
Setting Parameters by Example. 309-318
Electronic Edition (IEEE Computer Society DL) BibTeX
Zhi-Zhong Chen, Xin He, Chun-Hsi Huang:
Finding Double Euler Trails of Planar Graphs in Linear Time. 319-329
Electronic Edition (IEEE Computer Society DL) BibTeX
Karsten Weihe:
Edge-Disjoint Routing in Plane Switch Graphs in Linear Time. 330-340
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7B

John Watrous:
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. 341-351
Electronic Edition (IEEE Computer Society DL) BibTeX
Andris Ambainis:
A Better Lower Bound for Quantum Algorithms Searching an Ordered List. 352-357
Electronic Edition (IEEE Computer Society DL) BibTeX
Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka:
Bounds for Small-Error and Zero-Error Quantum Algorithms. 358-368
Electronic Edition (IEEE Computer Society DL) BibTeX
Ashwin Nayak:
Optimal Lower Bounds for Quantum Automata and Random Access Codes. 369-377
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8A

Moses Charikar, Sudipto Guha:
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. 378-388
Electronic Edition (IEEE Computer Society DL) BibTeX
Naoki Katoh, Takeshi Tokuyama:
Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications. 389-398
Electronic Edition (IEEE Computer Society DL) BibTeX
Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Cuts, Trees and l₁-Embeddings of Graphs. 399-409
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8B

Uwe Schöning:
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. 410-414
Electronic Edition (IEEE Computer Society DL) BibTeX
Eli Ben-Sasson, Russell Impagliazzo:
Random CNF's are Hard for the Polynomial Calculus. 415-421
Electronic Edition (IEEE Computer Society DL) BibTeX
Maria Luisa Bonet, Nicola Galesi:
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. 422-432
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 9A

S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
Online Scheduling to Minimize Average Stretch. 433-442
Electronic Edition (IEEE Computer Society DL) BibTeX
Elias Koutsoupias:
Weak Adversaries for the k-Server Problem. 444-449
Electronic Edition (IEEE Computer Society DL) BibTeX
Avrim Blum, Carl Burch, Adam Kalai:
Finely-Competitive Paging. 450-458
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 9B

Richard J. Lipton, Anastasios Viglas:
On the Complexity of SAT. 459-464
Electronic Edition (IEEE Computer Society DL) BibTeX
Christopher Umans:
Hardness of Approximating Sigma₂^p Minimization Problems. 465-474
Electronic Edition (IEEE Computer Society DL) BibTeX
Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. 475-485
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 10A

P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, Farrokh Vatan:
On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis. 486-494
Electronic Edition (IEEE Computer Society DL) BibTeX
Wojciech Plandowski:
Satisfiability of Word Equations with Constants is in PSPACE. 495-500
Electronic Edition (IEEE Computer Society DL) BibTeX
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
An Approximate L¹-Difference Algorithm for Massive Data Streams. 501-511
Electronic Edition (IEEE Computer Society DL) BibTeX
Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou:
Algorithmic Aspects of Protein Structure Similarity. 512-522
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 10B

Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer:
Magic Functions. 523-534
Electronic Edition (IEEE Computer Society DL) BibTeX
Jeong Han Kim, Daniel R. Simon, Prasad Tetali:
Limits on the Efficiency of One-Way Permutation-Based Hash Functions. 535-542
Electronic Edition (IEEE Computer Society DL) BibTeX
Amit Sahai:
Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. 543-553
Electronic Edition (IEEE Computer Society DL) BibTeX
Tomas Sander, Adam Young, Moti Yung:
Non-Interactive CryptoComputing For NC¹. 554-567
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 11A

Jon M. Kleinberg, Yuval Rabani, Éva Tardos:
Fairness in Routing and Load Balancing. 568-578
Electronic Edition (IEEE Computer Society DL) BibTeX
Ashish Goel, Piotr Indyk:
Stochastic Load Balancing and Related Problems. 579-586
Electronic Edition (IEEE Computer Society DL) BibTeX
Malwina J. Luczak, Eli Upfal:
Reducing Network Congestion and Blocking Probability Through Balanced Allocation. 587-595
Electronic Edition (IEEE Computer Society DL) BibTeX
Roman M. Kolpakov, Gregory Kucherov:
Finding Maximal Repetitions in a Word in Linear Time. 596-604
Electronic Edition (IEEE Computer Society DL) BibTeX
Avi Shoshan, Uri Zwick:
All Pairs Shortest Paths in Undirected Graphs with Integer Weights. 605-615
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 11B

Rosa I. Arriaga, Santosh Vempala:
An Algorithmic Theory of Learning: Robust Concepts and Random Projection. 616-623
Electronic Edition (IEEE Computer Society DL) BibTeX
Adam Klivans, Rocco A. Servedio:
Boosting and Hard-Core Sets. 624-633
Electronic Edition (IEEE Computer Society DL) BibTeX
Sanjoy Dasgupta:
Learning Mixtures of Gaussians. 634-644
Electronic Edition (IEEE Computer Society DL) BibTeX
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries. 645-655
Electronic Edition (IEEE Computer Society DL) BibTeX
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. 656-666
Electronic Edition (IEEE Computer Society DL) BibTeX