| 1998 | Concurrent Reachability Games. | Luca de Alfaro, Thomas A. Henzinger, Orna Kupferman |
| 1998 | Delayed Information and Action in On-line Algorithms. | Susanne Albers, Moses Charikar, Michael Mitzenmacher |
| 1998 | Parametric and Kinetic Minimum Spanning Trees. | Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, Monika Rauch Henzinger |
| 1998 | Protocols for Asymmetric Communication Channels. | Micah Adler, Bruce M. Maggs |
| 1997 | A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. | Santosh S. Vempala |
| 1997 | Approximating Shortest Paths on an Nonconvex Polyhedron. | Kasturi R. Varadarajan, Pankaj K. Agarwal |
| 1997 | Hamiltonian Cycles in Solid Grid Graphs. | Christopher Umans, William J. Lenhart |
| 1997 | Undirected Single Source Shortest Path in Linear Time. | Mikkel Thorup |
| 1997 | Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. | Aravind Srinivasan |
| 1997 | Deciding Properties of Polynomials Without Factoring. | Tomas Sander, Mohammad Amin Shokrollahi |
| 1997 | A Complete Promise Problem for Statistical Zero-Knowledge. | Amit Sahai, Salil P. Vadhan |
| 1997 | Making Nondeterminism Unambiguous. | Klaus Reinhardt, Eric Allender |
| 1997 | Separation of the Monotone NC Hierarchy. | Ran Raz, Pierre McKenzie |
| 1997 | Tight Bounds for Depth-two Superconcentrators. | Jaikumar Radhakrishnan, Amnon Ta-Shma |
| 1997 | Two Decades of Temporal Logic: Achievements and Challenges (Abstract). | Amir Pnueli |
| 1997 | Satisfiability Coding Lemma. | Ramamohan Paturi, Pavel Pudlk, Francis Zane |
| 1997 | A 2-Approximation Algorithm for the Directed Multiway Cut Problem. | Joseph Naor, Leonid Zosin |
| 1997 | Improved Approximations for Shallow-Light Spanning Trees. | Joseph Naor, Baruch Schieber |
| 1997 | Number-theoretic Constructions of Efficient Pseudo-random Functions. | Moni Naor, Omer Reingold |
| 1997 | Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. | J. Ian Munro, Venkatesh Raman |
| 1997 | Exploiting Locality for Data Management in Systems of Limited Bandwidth. | Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vcking, Matthias Westermann |
| 1997 | On the Complexity of a Set-Union Problem. | Richard J. Lipton, Paul J. Martino, Andy Neitzke |
| 1997 | Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. | Eyal Kushilevitz, Rafail Ostrovsky |
| 1997 | On the Power of Quantum Finite State Automata. | Attila Kondacs, John Watrous |
| 1997 | Improved Approximation Algorithms for Unsplittable Flow Problems. | Stavros G. Kolliopoulos, Clifford Stein |