| 2000 | A PCP characterization of NP with optimal amortized query complexity. Alex Samorodnitsky, Luca Trevisan |
| 2000 | A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. Satoru Iwata, Lisa Fleischer, Satoru Fujishige |
| 2000 | A constant factor approximation algorithm for a class of classification problems. Anupam Gupta, Éva Tardos |
| 2000 | A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. Leonid Gurvits, Alex Samorodnitsky |
| 2000 | A guessing game and randomized online algorithms. Steven S. Seiden |
| 2000 | A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. Jochen Könemann, R. Ravi |
| 2000 | A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). Meena Mahajan, Kasturi R. Varadarajan |
| 2000 | A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract). Artur Czumaj, Christian Scheideler |
| 2000 | A new proof of the weak pigeonhole principle. Alexis Maciel, Toniann Pitassi, Alan R. Woods |
| 2000 | A proof of the security of quantum key distribution (extended abstract). Eli Biham, Michel Boyer, P. Oscar Boykin, Tal Mor, Vwani P. Roychowdhury |
| 2000 | A random graph model for massive graphs. William Aiello, Fan R. K. Chung, Linyuan Lu |
| 2000 | A unified approach to approximating resource allocation and scheduling. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber |
| 2000 | Approximate nearest neighbors and sequence comparison with block operations. S. Muthukrishnan, Süleyman Cenk Sahinalp |
| 2000 | Approximating permanents of complex matrices. Martin Fürer |
| 2000 | Approximating the domatic number. Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz |
| 2000 | Approximating the minimum bisection size (extended abstract). Uriel Feige, Robert Krauthgamer, Kobbi Nissim |
| 2000 | Approximation algorithms for geometric shortest path problems. Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack |
| 2000 | Are bitvectors optimal? Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh |
| 2000 | Balanced allocations: the heavily loaded case. Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking |
| 2000 | Better algorithms for unfair metrical task systems and applications. Amos Fiat, Manor Mendel |
| 2000 | Circuit minimization problem. Valentine Kabanets, Jin-Yi Cai |
| 2000 | Clustering for edge-cost minimization (extended abstract). Leonard J. Schulman |
| 2000 | Combining fairness with throughput: online routing with multiple objectives. Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2000 | Complete characterization of security notions for probabilistic private-key encryption. Jonathan Katz, Moti Yung |
| 2000 | Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). Roberto Grossi, Jeffrey Scott Vitter |
| 2000 | Compression using efficient multicasting. Micah Adler, Frank Thomson Leighton |
| 2000 | Computing the median with uncertainty. Tomás Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, Jennifer Widom |
| 2000 | Computing with highly mixed states (extended abstract). Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani |
| 2000 | Connectivity and inference problems for temporal networks. David Kempe, Jon M. Kleinberg, Amit Kumar |
| 2000 | Exact computations of the inertia symmetric integer matrices. Steven Fortune |
| 2000 | Extractors and pseudo-random generators with optimal seed length. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 2000 | Faster suffix tree construction with missing suffix links. Richard Cole, Ramesh Hariharan |
| 2000 | Finding long paths and cycles in sparse Hamiltonian graphs. Tomás Feder, Rajeev Motwani, Carlos S. Subi |
| 2000 | Finding smooth integers in short intervals using CRT decoding. Dan Boneh |
| 2000 | From partial consistency to global broadcast. Matthias Fitzi, Ueli M. Maurer |
| 2000 | Hard-Potato routing. Costas Busch, Maurice Herlihy, Roger Wattenhofer |
| 2000 | Higher lower bounds on monotone size. Danny Harnik, Ran Raz |
| 2000 | How tall is a tree? Bruce A. Reed |
| 2000 | Improved algorithms for submodular function minimization and submodular flow. Lisa Fleischer, Satoru Iwata |
| 2000 | Improved approximations of crossings in graph drawings. Guy Even, Sudipto Guha, Baruch Schieber |
| 2000 | Improvements in throughout maximization for real-time scheduling. Piotr Berman, Bhaskar DasGupta |
| 2000 | Isomorphism testing for embeddable graphs through definability. Martin Grohe |
| 2000 | List decoding algorithms for certain concatenated codes. Venkatesan Guruswami, Madhu Sudan |
| 2000 | Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation. Vadim Olshevsky, Mohammad Amin Shokrollahi |
| 2000 | More general completeness theorems for secure two-party computation. Joe Kilian |
| 2000 | More theory revision with queries (extended abstract). Judy Goldsmith, Robert H. Sloan |
| 2000 | Near optimal multiple alignment within a band in polynomial time. Ming Li, Bin Ma, Lusheng Wang |
| 2000 | Near-optimal fully-dynamic graph connectivity. Mikkel Thorup |
| 2000 | Noise-tolerant learning, the parity problem, and the statistical query model. Avrim Blum, Adam Kalai, Hal Wasserman |
| 2000 | Normal subgroup reconstruction and quantum computation using group representations. Sean Hallgren, Alexander Russell, Amnon Ta-Shma |
| 2000 | On dual minimum cost flow algorithms (extended abstract). Jens Vygen |
| 2000 | On quantum and probabilistic communication: Las Vegas and one-way protocols. Hartmut Klauck |
| 2000 | On the approximability of the traveling salesman problem (extended abstract). Christos H. Papadimitriou, Santosh S. Vempala |
| 2000 | On the complexity of verifiable secret sharing and multiparty computation. Ronald Cramer, Ivan Damgård, Stefan Dziembowski |
| 2000 | On the decidability of accessibility problems (extended abstract). Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Venkatasubramanian |
| 2000 | On the efficiency of local decoding procedures for error-correcting codes. Jonathan Katz, Luca Trevisan |
| 2000 | On the sum-of-squares algorithm for bin packing. János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber |
| 2000 | On transformation of interactive proofs that preserve the prover's complexity. Salil P. Vadhan |
| 2000 | On zero-knowledge proofs (extended abstract): "from membership to decision". Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung |
| 2000 | Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Alexei Y. Kitaev, John Watrous |
| 2000 | Polynomial-time approximation scheme for data broadcast. Claire Kenyon, Nicolas Schabanel, Neal E. Young |
| 2000 | Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA F. Frances Yao, Eugene M. Luks |
| 2000 | Pseudo-random functions and factoring (extended abstract). Moni Naor, Omer Reingold, Alon Rosen |
| 2000 | Quantum bit escrow. Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao |
| 2000 | Quantum lower bounds by quantum arguments. Andris Ambainis |
| 2000 | Query strategies for priced information (extended abstract). Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai |
| 2000 | Random walks with "back buttons" (extended abstract). Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins |
| 2000 | Randomized metarounding (extended abstract). Robert D. Carr, Santosh S. Vempala |
| 2000 | Rapid sampling though quantum computing. Lov K. Grover |
| 2000 | Resettable zero-knowledge (extended abstract). Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali |
| 2000 | Satisfiability of equations in free groups is in PSPACE. Claudio Gutierrez |
| 2000 | Self-testing of universal and fault-tolerant sets of quantum gates. Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha |
| 2000 | Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). Dimitris Achlioptas |
| 2000 | Sharing the cost of muliticast transmissions (preliminary version). Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker |
| 2000 | Shortest path queries in planar graphs. Danny Z. Chen, Jinhui Xu |
| 2000 | Smoothing and cleaning up slivers. Herbert Edelsbrunner, Xiang-Yang Li, Gary L. Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, Alper Üngör, Noel Walkington |
| 2000 | Space complexity in propositional calculus. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract). Sorin Istrail |
| 2000 | Strictly non-blocking WDM cross-connects for heterogeneous networks. April Rasala, Gordon T. Wilfong |
| 2000 | The program-size complexity of self-assembled squares (extended abstract). Paul W. K. Rothemund, Erik Winfree |
| 2000 | The risk profile problem for stock portfolio optimization (extended abstract). Ming-Yang Kao, Andreas Nolte, Stephen R. Tate |
| 2000 | The small-world phenomenon: an algorithmic perspective. Jon M. Kleinberg |
| 2000 | The value of strong inapproximability results for clique. Aravind Srinivasan |
| 2000 | Tight(er) worst-case bounds on dynamic searching and priority queues. Arne Andersson, Mikkel Thorup |
| 2000 | Tighter bounds for nearest neighbor search and related problems in the cell probe model. Omer Barkol, Yuval Rabani |
| 2000 | epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract). James B. Orlin, Andreas S. Schulz, Sudipta Sengupta |