41. FOCS 2000: Redondo Beach, CA, USA

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, Salil P. Vadhan:
  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, 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
  
• 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, 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

• 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, C. Greg Plaxton:
  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 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(n²) 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 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, 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
  
• 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, Maria Minkoff:
  Building Steiner Trees with Incomplete Global Knowledge. 613-623
  
• Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
  Cost-Distance: Two Metric Network Design. 624-630
  
• 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
  
• Maurice Herlihy, Eric Ruppert:
  On the Existence of Booster Types. 653-663
  
• 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
  

Last update Mon May 20 14:41:49 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page