| 2000 | "Soft-decision" Decoding of Chinese Remainder Codes. | Venkatesan Guruswami, Amit Sahai, Madhu Sudan |
| 2000 | Hardness of Approximate Hypergraph Coloring. | Venkatesan Guruswami, Johan Hstad, Madhu Sudan |
| 2000 | Clustering Data Streams. | Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan |
| 2000 | Hierarchical Placement and Network Design Problems. | Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2000 | Nested Graph Dissection and Approximation Algorithms. | Sudipto Guha |
| 2000 | Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. | Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick |
| 2000 | The Relationship between Public Key Encryption and Oblivious Transfer. | Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan |
| 2000 | Lower Bounds on the Efficiency of Generic Cryptographic Constructions. | Rosario Gennaro, Luca Trevisan |
| 2000 | Concurrent Oblivious Transfer. | Juan A. Garay, Philip D. MacKenzie |
| 2000 | Using Expander Graphs to Find Vertex Connectivity. | Harold N. Gabow |
| 2000 | The Randomness Recycler: A New Technique for Perfect Sampling. | James Allen Fill, Mark Huber |
| 2000 | Opportunistic Data Structures with Applications. | Paolo Ferragina, Giovanni Manzini |
| 2000 | A polylogarithmic approximation of the minimum bisection. | Uriel Feige, Robert Krauthgamer |
| 2000 | Topological Persistence and Simplification. | Herbert Edelsbrunner, David Letscher, Afra Zomorodian |
| 2000 | Computing the Determinant and Smith Form of an Integer Matrix. | Wayne Eberly, Mark Giesbrecht, Gilles Villard |
| 2000 | Zaps and Their Applications. | Cynthia Dwork, Moni Naor |
| 2000 | Fully Dynamic Transitive Closure: Breaking Through the O(n | Camil Demetrescu, Giuseppe F. Italiano |
| 2000 | Straighting Polygonal Arcs and Convexifying Polygonal Cycles. | Robert Connelly, Erik D. Demaine, Gnter Rote |
| 2000 | Fast parallel circuits for the quantum Fourier transform. | Richard Cleve, John Watrous |
| 2000 | Fast Broadcasting and Gossiping in Radio Networks. | Marek Chrobak, Leszek Gasieniec, Wojciech Rytter |
| 2000 | Combinatorial feature selection problems. | Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai |
| 2000 | On Levels in Arrangements of Curves. | Timothy M. Chan |
| 2000 | Cache-Oblivious B-Trees. | Michael A. Bender, Erik D. Demaine, Martin Farach-Colton |
| 2000 | Super-linear time-space tradeoff lower bounds for randomized computation. | Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee |
| 2000 | Testing that distributions are close. | Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White |