| 1997 | Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. | Russ Bubley, Martin E. Dyer |
| 1997 | Parallelizing Elimination Orders with Linear Fill. | Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi |
| 1997 | No Feasible Interpolation for TC0-Frege Proofs. | Maria Luisa Bonet, Toniann Pitassi, Ran Raz |
| 1997 | Does Parallel Repetition Lower the Error in Computationally Sound Protocols? | Mihir Bellare, Russell Impagliazzo, Moni Naor |
| 1997 | A Concrete Security Treatment of Symmetric Encryption. | Mihir Bellare, Anand Desai, E. Jokipii, Phillip Rogaway |
| 1997 | An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. | Saugata Basu |
| 1997 | Global Optimization Using Local Information with Applications to Flow Control. | Yair Bartal, John W. Byers, Danny Raz |
| 1997 | Edge-Connectivity Augmentation Preserving Simplicity. | Jrgen Bang-Jensen, Tibor Jordn |
| 1997 | Buy-at-Bulk Network Design. | Baruch Awerbuch, Yossi Azar |
| 1997 | Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. | Sanjeev Arora |
| 1997 | General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). | Matthew Andrews, Antonio Fernndez, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang |
| 1997 | Weak Random Sources, Hitting Sets, and BPP Simulations. | Alexander E. Andreev, Andrea E. F. Clementi, Jos D. P. Rolim, Luca Trevisan |
| 1997 | Pattern Matching with Swaps. | Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein |
| 1997 | Nearly Tight Bounds on the Learnability of Evolution. | Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan |
| 1997 | Alternating-time Temporal Logic. | Rajeev Alur, Thomas A. Henzinger, Orna Kupferman |
| 1997 | The Competitive Analysis of Risk Taking with Applications to Online Trading. | Sabah al-Binali |
| 1997 | The Analysis of a List-Coloring Algorithm on a Random Graph. | Dimitris Achlioptas, Michael S. O. Molloy |
| 1996 | An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups. | Vijay V. Vazirani, Huzur Saran, B. Sundar Rajan |
| 1996 | Gadgets, Approximation, and Linear Programming (extended abstract). | Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson |
| 1996 | Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. | Denis Thrien, Thomas Wilke |
| 1996 | Maximum Likelihood Decoding of Reed Solomon Codes. | Madhu Sudan |
| 1996 | Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. | Daniel A. Spielman, Shang-Hua Teng |
| 1996 | Highly Fault-Tolerant Parallel Computation (extended abstract). | Daniel A. Spielman |
| 1996 | Fault-Tolerant Quantum Computation. | Peter W. Shor |
| 1996 | Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (extended abstract). | Sleyman Cenk Sahinalp, Uzi Vishkin |