41. FOCS 2000: Redondo Beach, CA, USA

41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA. IEEE Computer Society, 2000, ISBN 0-7695-0850-2

Session 1

Omer Reingold, Salil P. Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. 3-13 BibTeX
Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi: Universality and Tolerance. 14-21 BibTeX
Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. 22-31 BibTeX
Luca Trevisan, Salil P. Vadhan: Extracting Randomness from Samplable Distributions. 32-42 BibTeX
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. 43-53 BibTeX

Session 2

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal: Random graph models for the web graph. 57-65 BibTeX
Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker: Optimization Problems in Congestion Control. 66-74 BibTeX
Amit Kumar, Jon M. Kleinberg: Fairness Measures for Resource Allocation. 75-85 BibTeX
Christos H. Papadimitriou, Mihalis Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. 86-92 BibTeX
Tim Roughgarden, Éva Tardos: How Bad is Selfish Routing? 93-102 BibTeX

Session 3

Uriel Feige, Robert Krauthgamer: A polylogarithmic approximation of the minimum bisection. 105-115 BibTeX
Maxim Sviridenko, Gerhard J. Woeginger: Approximability and in-approximability results for no-wait shop scheduling. 116-125 BibTeX
Sudipto Guha: Nested Graph Dissection and Approximation Algorithms. 126-135 BibTeX
Martin Skutella: Approximating the single source unsplittable min-cost flow problem. 136-145 BibTeX

Session 4

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. 149-158 BibTeX
Venkatesan Guruswami, Amit Sahai, Madhu Sudan: "Soft-decision" Decoding of Chinese Remainder Codes. 159-168 BibTeX
Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee: Super-linear time-space tradeoff lower bounds for randomized computation. 169-179 BibTeX
Jacobo Torán: On the Hardness of Graph Isomorphism. 180-186 BibTeX

Session 5

Piotr Indyk: Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. 189-197 BibTeX
Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe: New Data Structures for Orthogonal Range Searching. 198-207 BibTeX
Sunil Arya, Theocharis Malamatos, David M. Mount: Nearly Optimal Expected-Case Planar Point Location. 208-218 BibTeX
Timothy M. Chan: On Levels in Arrangements of Curves. 219-227 BibTeX

Session 7

Jon M. Kleinberg: Detecting a Network Failure. 231-239 BibTeX
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron: Testing of Clustering. 240-250 BibTeX
Ilan Newman: Testing of Functions that have small width Branching Programs. 251-258 BibTeX
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. 259-269 BibTeX
Peter Auer: Using Upper Confidence Bounds for Online Learning. 270-279 BibTeX

Session 7

Cynthia Dwork, Moni Naor: Zaps and Their Applications. 283-293 BibTeX
Yuval Ishai, Eyal Kushilevitz: Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. 294-304 BibTeX
Rosario Gennaro, Luca Trevisan: Lower Bounds on the Efficiency of Generic Cryptographic Constructions. 305-313 BibTeX
Juan A. Garay, Philip D. MacKenzie: Concurrent Oblivious Transfer. 314-324 BibTeX
Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan: The Relationship between Public Key Encryption and Oblivious Transfer. 325-335 BibTeX

Session 8

Ramgopal R. Mettu, C. Greg Plaxton: The Online Median Problem. 339-348 BibTeX
Rafail Ostrovsky, Yuval Rabani: Polynomial Time Approximation Schemes for Geometric k-Clustering. 349-358 BibTeX
Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams. 359-366 BibTeX
Ravi Kannan, Santosh Vempala, Adrian Vetta: On Clusterings - Good, Bad and Spectral. 367-377 BibTeX

Session 9

Camil Demetrescu, Giuseppe F. Italiano: Fully Dynamic Transitive Closure: Breaking Through the O(n²) Barrier. 381-389 BibTeX
Paolo Ferragina, Giovanni Manzini: Opportunistic Data Structures with Applications. 390-398 BibTeX
Michael A. Bender, Erik D. Demaine, Martin Farach-Colton: Cache-Oblivious B-Trees. 399-409 BibTeX
Harold N. Gabow: Using Expander Graphs to Find Vertex Connectivity. 410-420 BibTeX

Session 10

János Pach, Gábor Tardos: On the boundary complexity of the union of fat triangles. 423-431 BibTeX
Robert Connelly, Erik D. Demaine, Günter Rote: Straighting Polygonal Arcs and Convexifying Polygonal Cycles. 432-442 BibTeX
Ileana Streinu: A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning. 443-453 BibTeX
Herbert Edelsbrunner, David Letscher, Afra Zomorodian: Topological Persistence and Simplification. 454-463 BibTeX

Session 11

Jeff Kahn, Jeong Han Kim, László Lovász, Van H. Vu: The Cover Time, the Blanket Time, and the Matthews Bound. 467-475 BibTeX
Igor Pak: The product replacement algorithm is polynomial. 476-485 BibTeX
Adam Kalai, Santosh Vempala: Efficient Algorithms for Universal Portfolios. 486-491 BibTeX
Russell A. Martin, Dana Randall: Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method. 492-502 BibTeX
James Allen Fill, Mark Huber: The Randomness Recycler: A New Technique for Perfect Sampling. 503-511 BibTeX

Session 12

Lisa Hales, Sean Hallgren: An Improved Quantum Fourier Transform Algorithm and Applications. 515-525 BibTeX
Richard Cleve, John Watrous: Fast parallel circuits for the quantum Fourier transform. 526-536 BibTeX
John Watrous: Succinct quantum proofs for properties of finite groups. 537-546 BibTeX
Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf: Private Quantum Channels. 547-553 BibTeX
Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh: The Quantum Complexity of Set Membership. 554-562 BibTeX

Session 13

Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking: Randomized Rumor Spreading. 565-574 BibTeX
Marek Chrobak, Leszek Gasieniec, Wojciech Rytter: Fast Broadcasting and Gossiping in Radio Networks. 575-581 BibTeX
Claire Kenyon, Michael Mitzenmacher: Linear Waste of Best Fit Bin Packing on Skewed Distributions. 582-589 BibTeX
Dimitris Achlioptas, Gregory B. Sorkin: Optimal myopic algorithms for random 3-SAT. 590-600 BibTeX

Session 14

Sudipto Guha, Adam Meyerson, Kamesh Munagala: Hierarchical Placement and Network Design Problems. 603-612 BibTeX
David R. Karger, Maria Minkoff: Building Steiner Trees with Incomplete Global Knowledge. 613-623 BibTeX
Adam Meyerson, Kamesh Munagala, Serge A. Plotkin: Cost-Distance: Two Metric Network Design. 624-630 BibTeX
Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai: Combinatorial feature selection problems. 631-640 BibTeX

Session 15

Monika Maidl: The Common Fragment of CTL and LTL. 643-652 BibTeX
Maurice Herlihy, Eric Ruppert: On the Existence of Booster Types. 653-663 BibTeX
Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick: Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. 664-674 BibTeX
Wayne Eberly, Mark Giesbrecht, Gilles Villard: Computing the Determinant and Smith Form of an Integer Matrix. 675-685 BibTeX