| 1997 | A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. | Mikls Ajtai, Cynthia Dwork |
| 1997 | Fault-Tolerant Quantum Computation With Constant Error. | Dorit Aharonov, Michael Ben-Or |
| 1997 | Reducing the Complexity of Reductions. | Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich |
| 1996 | Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. | David Zuckerman |
| 1996 | Generating Random Spanning Trees More Quickly than the Cover Time. | David Bruce Wilson |
| 1996 | Efficient 3-D Range Searching in External Memory. | Darren Erik Vengroff, Jeffrey Scott Vitter |
| 1996 | On Extracting Randomness From Weak Random Sources (Extended Abstract). | Amnon Ta-Shma |
| 1996 | Faster Isomorphism Testing of Strongly Regular Graphs. | Daniel A. Spielman |
| 1996 | A Tight Analysis of the Greedy Algorithm for Set Cover. | Petr Slavk |
| 1996 | Efficiently Four-Coloring Planar Graphs. | Neil Robertson, Daniel P. Sanders, Paul D. Seymour, Robin Thomas |
| 1996 | Distributed Packet Switching in Arbitrary Networks. | Yuval Rabani, va Tardos |
| 1996 | On Relationships between Statistical Zero-Knowledge Proofs. | Tatsuaki Okamoto |
| 1996 | The PL Hierarchy Collapses. | Mitsunori Ogihara |
| 1996 | Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). | Ilan Newman, Mario Szegedy |
| 1996 | Evaluation May Be Easier Than Generation (Extended Abstract). | Moni Naor |
| 1996 | Deterministic | Hiroshi Nagamochi, Toshihide Ibaraki |
| 1996 | Embedding Graphs in an Arbitrary Surface in Linear Time. | Bojan Mohar |
| 1996 | Translational Polygon Containment and Minimal Enclosure using Linear Programming Based Restriction. | Victor Milenkovic |
| 1996 | Fast Algorithms for Parametric Scheduling Come from Extensions to Parametric Maximum Flow. | S. Thomas McCormick |
| 1996 | An | Yuan Ma |
| 1996 | Non-Expansive Hashing. | Nathan Linial, Ori Sasson |
| 1996 | Characterizing Linear Size Circuits in Terms of Privacy. | Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosn |
| 1996 | The Linear-Array Conjecture in Communication Complexity is False. | Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky |
| 1996 | Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees (Correction). | S. Rao Kosaraju, Arthur L. Delcher |
| 1996 | Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. | Philip N. Klein, Hsueh-I Lu |