| 2000 | "Soft-decision" Decoding of Chinese Remainder Codes. Venkatesan Guruswami, Amit Sahai, Madhu Sudan |
| 2000 | 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, 2000 |
| 2000 | A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning. Ileana Streinu |
| 2000 | A polylogarithmic approximation of the minimum bisection. Uriel Feige, Robert Krauthgamer |
| 2000 | An Improved Quantum Fourier Transform Algorithm and Applications. Lisa Hales, Sean Hallgren |
| 2000 | Approximability and in-approximability results for no-wait shop scheduling. Maxim Sviridenko, Gerhard J. Woeginger |
| 2000 | Approximating the single source unsplittable min-cost flow problem. Martin Skutella |
| 2000 | Building Steiner Trees with Incomplete Global Knowledge. David R. Karger, Maria Minkoff |
| 2000 | Cache-Oblivious B-Trees. Michael A. Bender, Erik D. Demaine, Martin Farach-Colton |
| 2000 | Clustering Data Streams. Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan |
| 2000 | Combinatorial feature selection problems. Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai |
| 2000 | Computing the Determinant and Smith Form of an Integer Matrix. Wayne Eberly, Mark Giesbrecht, Gilles Villard |
| 2000 | Concurrent Oblivious Transfer. Juan A. Garay, Philip D. MacKenzie |
| 2000 | Cost-Distance: Two Metric Network Design. Adam Meyerson, Kamesh Munagala, Serge A. Plotkin |
| 2000 | Detecting a Network Failure. Jon M. Kleinberg |
| 2000 | Efficient Algorithms for Universal Portfolios. Adam Kalai, Santosh S. Vempala |
| 2000 | Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2000 | Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick |
| 2000 | Extracting Randomness from Samplable Distributions. Luca Trevisan, Salil P. Vadhan |
| 2000 | Extracting Randomness via Repeated Condensing. Omer Reingold, Ronen Shaltiel, Avi Wigderson |
| 2000 | Fairness Measures for Resource Allocation. Amit Kumar, Jon M. Kleinberg |
| 2000 | Fast Broadcasting and Gossiping in Radio Networks. Marek Chrobak, Leszek Gasieniec, Wojciech Rytter |
| 2000 | Fast parallel circuits for the quantum Fourier transform. Richard Cleve, John Watrous |
| 2000 | Fully Dynamic Transitive Closure: Breaking Through the O(n Camil Demetrescu, Giuseppe F. Italiano |
| 2000 | Hardness of Approximate Hypergraph Coloring. Venkatesan Guruswami, Johan Håstad, Madhu Sudan |
| 2000 | Hierarchical Placement and Network Design Problems. Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2000 | How Bad is Selfish Routing? Tim Roughgarden, Éva Tardos |
| 2000 | Linear Waste of Best Fit Bin Packing on Skewed Distributions. Claire Kenyon, Michael Mitzenmacher |
| 2000 | Lower Bounds on the Efficiency of Generic Cryptographic Constructions. Rosario Gennaro, Luca Trevisan |
| 2000 | Nearly Optimal Expected-Case Planar Point Location. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2000 | Nested Graph Dissection and Approximation Algorithms. Sudipto Guha |
| 2000 | New Data Structures for Orthogonal Range Searching. Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe |
| 2000 | On Clusterings - Good, Bad and Spectral. Ravi Kannan, Santosh S. Vempala, Adrian Vetta |
| 2000 | On Levels in Arrangements of Curves. Timothy M. Chan |
| 2000 | On the Approximability of Trade-offs and Optimal Access of Web Sources. Christos H. Papadimitriou, Mihalis Yannakakis |
| 2000 | On the Existence of Booster Types. Maurice Herlihy, Eric Ruppert |
| 2000 | On the Hardness of Graph Isomorphism. Jacobo Torán |
| 2000 | On the boundary complexity of the union of fat triangles. János Pach, Gábor Tardos |
| 2000 | Opportunistic Data Structures with Applications. Paolo Ferragina, Giovanni Manzini |
| 2000 | Optimal myopic algorithms for random 3-SAT. Dimitris Achlioptas, Gregory B. Sorkin |
| 2000 | Optimization Problems in Congestion Control. Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker |
| 2000 | Polynomial Time Approximation Schemes for Geometric k-Clustering. Rafail Ostrovsky, Yuval Rabani |
| 2000 | Private Quantum Channels. Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf |
| 2000 | Pseudorandom Generators in Propositional Proof Complexity. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | Random graph models for the web graph. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal |
| 2000 | Randomized Rumor Spreading. Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking |
| 2000 | Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. Yuval Ishai, Eyal Kushilevitz |
| 2000 | Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method. Russell A. Martin, Dana Randall |
| 2000 | Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. Piotr Indyk |
| 2000 | Straighting Polygonal Arcs and Convexifying Polygonal Cycles. Robert Connelly, Erik D. Demaine, Günter Rote |
| 2000 | Succinct quantum proofs for properties of finite groups. John Watrous |
| 2000 | Super-linear time-space tradeoff lower bounds for randomized computation. Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee |
| 2000 | Testing of Clustering. Noga Alon, Seannie Dar, Michal Parnas, Dana Ron |
| 2000 | Testing of Functions that have small width Branching Programs. Ilan Newman |
| 2000 | Testing that distributions are close. Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White |
| 2000 | The Common Fragment of CTL and LTL. Monika Maidl |
| 2000 | The Cover Time, the Blanket Time, and the Matthews Bound. Jeff Kahn, Jeong Han Kim, László Lovász, Van H. Vu |
| 2000 | The Online Median Problem. Ramgopal R. Mettu, C. Greg Plaxton |
| 2000 | The Quantum Complexity of Set Membership. Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh |
| 2000 | The Randomness Recycler: A New Technique for Perfect Sampling. James Allen Fill, Mark Huber |
| 2000 | The Relationship between Public Key Encryption and Oblivious Transfer. Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan |
| 2000 | The product replacement algorithm is polynomial. Igor Pak |
| 2000 | Topological Persistence and Simplification. Herbert Edelsbrunner, David Letscher, Afra Zomorodian |
| 2000 | Universality and Tolerance. Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi |
| 2000 | Using Expander Graphs to Find Vertex Connectivity. Harold N. Gabow |
| 2000 | Using Upper Confidence Bounds for Online Learning. Peter Auer |
| 2000 | Zaps and Their Applications. Cynthia Dwork, Moni Naor |