default search action
41st 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 - Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski
, Endre Szemerédi:
Universality and Tolerance. 14-21 - Omer Reingold, Ronen Shaltiel, Avi Wigderson:
Extracting Randomness via Repeated Condensing. 22-31 - Luca Trevisan
Extracting Randomness from Samplable Distributions. 32-42 - Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. 43-53
Session 2
- Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal:
Random graph models for the web graph. 57-65 - Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker:
Optimization Problems in Congestion Control. 66-74 - Amit Kumar, Jon M. Kleinberg:
Fairness Measures for Resource Allocation. 75-85 - Christos H. Papadimitriou, Mihalis Yannakakis:
On the Approximability of Trade-offs and Optimal Access of Web Sources. 86-92 - Tim Roughgarden, Éva Tardos:
How Bad is Selfish Routing? 93-102
Session 3
- Uriel Feige, Robert Krauthgamer:
A polylogarithmic approximation of the minimum bisection. 105-115 - Maxim Sviridenko, Gerhard J. Woeginger:
Approximability and in-approximability results for no-wait shop scheduling. 116-125 - Sudipto Guha:
Nested Graph Dissection and Approximation Algorithms. 126-135 - Martin Skutella:
Approximating the single source unsplittable min-cost flow problem. 136-145
Session 4
- Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. 149-158 - Venkatesan Guruswami, Amit Sahai, Madhu Sudan:
"Soft-decision" Decoding of Chinese Remainder Codes. 159-168 - Paul Beame
Super-linear time-space tradeoff lower bounds for randomized computation. 169-179 - Jacobo Torán:
On the Hardness of Graph Isomorphism. 180-186
Session 5
- Piotr Indyk:
Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. 189-197 - Stephen Alstrup, Gerth Stølting Brodal
New Data Structures for Orthogonal Range Searching. 198-207 - Sunil Arya, Theocharis Malamatos, David M. Mount:
Nearly Optimal Expected-Case Planar Point Location. 208-218 - Timothy M. Chan:
On Levels in Arrangements of Curves. 219-227
Session 7
- Jon M. Kleinberg:
Detecting a Network Failure. 231-239 - Noga Alon, Seannie Dar, Michal Parnas, Dana Ron:
Testing of Clustering. 240-250 - Ilan Newman:
Testing of Functions that have small width Branching Programs. 251-258 - Tugkan Batu
Testing that distributions are close. 259-269 - Peter Auer:
Using Upper Confidence Bounds for Online Learning. 270-279
Session 7
- Cynthia Dwork, Moni Naor:
Zaps and Their Applications. 283-293 - Yuval Ishai, Eyal Kushilevitz:
Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. 294-304 - Rosario Gennaro, Luca Trevisan
Lower Bounds on the Efficiency of Generic Cryptographic Constructions. 305-313 - Juan A. Garay, Philip D. MacKenzie:
Concurrent Oblivious Transfer. 314-324 - Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan:
The Relationship between Public Key Encryption and Oblivious Transfer. 325-335
Session 8
- Ramgopal R. Mettu
The Online Median Problem. 339-348 - Rafail Ostrovsky, Yuval Rabani
Polynomial Time Approximation Schemes for Geometric k-Clustering. 349-358 - Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan:
Clustering Data Streams. 359-366 - Ravi Kannan, Santosh S. Vempala, Adrian Vetta:
On Clusterings - Good, Bad and Spectral. 367-377
Session 9
- Camil Demetrescu, Giuseppe F. Italiano:
Fully Dynamic Transitive Closure: Breaking Through the O(n2) Barrier. 381-389 - Paolo Ferragina, Giovanni Manzini:
Opportunistic Data Structures with Applications. 390-398 - Michael A. Bender, Erik D. Demaine, Martin Farach-Colton
Cache-Oblivious B-Trees. 399-409 - Harold N. Gabow:
Using Expander Graphs to Find Vertex Connectivity. 410-420
Session 10
- János Pach, Gábor Tardos
On the boundary complexity of the union of fat triangles. 423-431 - Robert Connelly, Erik D. Demaine, Günter Rote:
Straighting Polygonal Arcs and Convexifying Polygonal Cycles. 432-442 - Ileana Streinu:
A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning. 443-453 - Herbert Edelsbrunner, David Letscher, Afra Zomorodian:
Topological Persistence and Simplification. 454-463
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 - Igor Pak:
The product replacement algorithm is polynomial. 476-485 - Adam Kalai, Santosh S. Vempala:
Efficient Algorithms for Universal Portfolios. 486-491 - Russell A. Martin, Dana Randall:
Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method. 492-502 - James Allen Fill, Mark Huber:
The Randomness Recycler: A New Technique for Perfect Sampling. 503-511
Session 12
- Lisa Hales, Sean Hallgren:
An Improved Quantum Fourier Transform Algorithm and Applications. 515-525 - Richard Cleve, John Watrous:
Fast parallel circuits for the quantum Fourier transform. 526-536 - John Watrous:
Succinct quantum proofs for properties of finite groups. 537-546 - Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf:
Private Quantum Channels. 547-553 - Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh:
The Quantum Complexity of Set Membership. 554-562
Session 13
- Richard M. Karp, Christian Schindelhauer
Randomized Rumor Spreading. 565-574 - Marek Chrobak, Leszek Gasieniec, Wojciech Rytter:
Fast Broadcasting and Gossiping in Radio Networks. 575-581 - Claire Kenyon, Michael Mitzenmacher:
Linear Waste of Best Fit Bin Packing on Skewed Distributions. 582-589 - Dimitris Achlioptas, Gregory B. Sorkin
Optimal myopic algorithms for random 3-SAT. 590-600
Session 14
- Sudipto Guha, Adam Meyerson, Kamesh Munagala
Hierarchical Placement and Network Design Problems. 603-612 - David R. Karger
Building Steiner Trees with Incomplete Global Knowledge. 613-623 - Adam Meyerson, Kamesh Munagala
Cost-Distance: Two Metric Network Design. 624-630 - Moses Charikar
Combinatorial feature selection problems. 631-640
Session 15
- Monika Maidl:
The Common Fragment of CTL and LTL. 643-652 - Maurice Herlihy, Eric Ruppert:
On the Existence of Booster Types. 653-663 - Georg Gottlob
Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. 664-674 - Wayne Eberly, Mark Giesbrecht, Gilles Villard:
Computing the Determinant and Smith Form of an Integer Matrix. 675-685
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-26 23:57 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: