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
- Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi: Universality and Tolerance. 14-21
- 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
- Christos H. Papadimitriou, Mihalis Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. 86-92
Session 3
- 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, Michael E. Saks, Xiaodong Sun, Erik Vee: 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, Theis Rauhe: 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
- Ilan Newman: Testing of Functions that have small width Branching Programs. 251-258
- Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. 259-269
- Peter Auer: Using Upper Confidence Bounds for Online Learning. 270-279
Session 7
- 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
- Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan: The Relationship between Public Key Encryption and Oblivious Transfer. 325-335
Session 8
- Rafail Ostrovsky, Yuval Rabani: Polynomial Time Approximation Schemes for Geometric k-Clustering. 349-358
Session 9
- Camil Demetrescu, Giuseppe F. Italiano: Fully Dynamic Transitive Closure: Breaking Through the O(n2) Barrier. 381-389
- Harold N. Gabow: Using Expander Graphs to Find Vertex Connectivity. 410-420
Session 10
- 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
- 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
- John Watrous: Succinct quantum proofs for properties of finite groups. 537-546
- Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh: The Quantum Complexity of Set Membership. 554-562
Session 13
- Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking: 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
Session 14
- Sudipto Guha, Adam Meyerson, Kamesh Munagala: Hierarchical Placement and Network Design Problems. 603-612
- Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai: Combinatorial feature selection problems. 631-640
Session 15
- Monika Maidl: The Common Fragment of CTL and LTL. 643-652
- Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick: 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-17T203624 by the dblp team