| 1991 | Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty | Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer |
| 1991 | Counting Networks and Multi-Processor Coordination | James Aspnes, Maurice Herlihy, Nir Shavit |
| 1991 | The Expressive Power of Voting Polynomials | James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich |
| 1991 | Searching in the Presence of Linearly Bounded Errors (Extended Abstract) | Javed A. Aslam, Aditi Dhagat |
| 1991 | Sampling and Integration of Near Log-Concave functions | David L. Applegate, Ravi Kannan |
| 1991 | When Won't Membership Queries Help? (Extended Abstract) | Dana Angluin, Michael Kharitonov |
| 1991 | Wait-free Parallel Algorithms for the Union-Find Problem | Richard J. Anderson, Heather Woll |
| 1991 | When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks | Ajit Agrawal, Philip N. Klein, R. Ravi |
| 1991 | Factoring Numbers Using Singular Integers | Leonard M. Adleman |
| 1991 | Generic Computation and Its Complexity | Serge Abiteboul, Victor Vianu |
| 1990 | A Technique for Lower Bounding the Cover Time | David Zuckerman |
| 1990 | Coherent Functions and Program Checkers (Extended Abstract) | Andrew Chi-Chih Yao |
| 1990 | Optimal Disk I/O with Parallel Block Transfer (Extended Abstract) | Jeffrey Scott Vitter, Elizabeth A. M. Shriver |
| 1990 | Deterministic Sampling-A New Technique for Fast Pattern Matching | Uzi Vishkin |
| 1990 | Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates | Mario Szegedy |
| 1990 | Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences | Rajamani Sundar, Robert Endre Tarjan |
| 1990 | Searching for Primitive Roots in Finite Fields | Victor Shoup |
| 1990 | The Discrete Log is Very Discreet | A. W. Schrift, Adi Shamir |
| 1990 | The Analysis of Closed Hashing under Limited Randomness (Extended Abstract) | Jeanette P. Schmidt, Alan Siegel |
| 1990 | One-Way Functions are Necessary and Sufficient for Secure Signatures | John Rompel |
| 1990 | Monotone Circuits for Matching Require Linear Depth | Ran Raz, Avi Wigderson |
| 1990 | Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines | Johannes A. La Poutr |
| 1990 | On the Complexity of Local Search (Extended Abstract) | Christos H. Papadimitriou, Alejandro A. Schffer, Mihalis Yannakakis |
| 1990 | Quantifiers and Approximation (Extended Abstract) | Alessandro Panconesi, Desh Ranjan |
| 1990 | Efficient Computation on Oblivious RAMs | Rafail Ostrovsky |