| 2000 | Average Bit-Complexity of Euclidean Algorithms. | Ali Akhavi, Brigitte Valle |
| 2000 | Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. | William Aiello, Sandeep N. Bhatt, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan |
| 2000 | Tight Size Bounds for Packet Headers in Narrow Meshes. | Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson |
| 2000 | Parsing Context-Sensitive NCE Graph Grammars. | Yoshihiro Adachi, Suguru Kobayashi |
| 2000 | Two-coloring Random Hypergraphs. | Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali |
| 2000 | Game Semantics: Achievements and Prospects. | Samson Abramsky |
| 2000 | On Complexity of Regular (1, +k)-Branching Programs. | Farid M. Ablayev |
| 1999 | An FPTAS for Agreeably Weighted Variance on a Single Machine. | Gerhard J. Woeginger |
| 1999 | The Wave Propagator Is Turing Computable. | Klaus Weihrauch, Ning Zhong |
| 1999 | From Computational Learning Theory to Discovery Science. | Osamu Watanabe |
| 1999 | Online Data Structures in External Memory. | Jeffrey Scott Vitter |
| 1999 | On the Complexity and Inapproximability of Shortest Implicant Problems. | Christopher Umans |
| 1999 | Erratum: Bulk-synchronous Parallel Multiplication of Boolean Matrices. | Alexandre Tiskin |
| 1999 | Many-Valued Logics and Holographic Proofs. | Mario Szegedy |
| 1999 | T(A) = T(B)? | Graud Snizergues |
| 1999 | Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP. | Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
| 1999 | Accessing Multiple Sequences Through Set Associative Caches. | Peter Sanders |
| 1999 | Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously. | Jan J. M. M. Rutten |
| 1999 | DNA Computing: New Ideas and Paradigms. | Grzegorz Rozenberg, Arto Salomaa |
| 1999 | Typed Exeptions and Continuations Cannot Macro-Express Each Other. | Jon G. Riecke, Hayo Thielecke |
| 1999 | Closed Freyd- and kappa-categories. | John Power, Hayo Thielecke |
| 1999 | A Variant of the Arrow Distributed Directory with Low Average Complexity. | David Peleg, Eilon Reshef |
| 1999 | Finite Automata with Generalized Acceptance Criteria. | Timo Peichl, Heribert Vollmer |
| 1999 | Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time. | Rasmus Pagh |
| 1999 | Polynomial and Rational Evaluation and Interpolation (with Structured Matrices). | Vadim Olshevsky, Victor Y. Pan |