| 1991 | Lower Bounds for Data Structure Problems on RAMs (Extended Abstract) | Amir M. Ben-Amram, Zvi Galil |
| 1991 | On ACC | Richard Beigel, Jun Tarui |
| 1991 | Languages that Are Easier than their Proofs | Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser |
| 1991 | On-line Scheduling in the Presence of Overload | Sanjoy K. Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis E. Shasha |
| 1991 | Approximate Representation Theory of Finite Groups | Lszl Babai, Katalin Friedl |
| 1991 | Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract) | Baruch Awerbuch, George Varghese |
| 1991 | The Maintenance of Common Data in a Distributed System | Baruch Awerbuch, Leonard J. Schulman |
| 1991 | Self-Stabilization By Local Checking and Correction (Extended Abstract) | Baruch Awerbuch, Boaz Patt-Shamir, George Varghese |
| 1991 | Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract) | Yonatan Aumann, Michael Ben-Or |
| 1991 | Faster Uniquely Represented Dictionaries | Arne Andersson, Thomas Ottmann |
| 1991 | Adaptive Dictionary Matching | Amihood Amir, Martin Farach |
| 1991 | On the Exponent of the All Pairs Shortest Path Problem | Noga Alon, Zvi Galil, Oded Margalit |
| 1991 | A parallel algorithmic version of the Local Lemma | Noga Alon |
| 1991 | Exact Learning of Read-Twice DNF Formulas (Extended Abstract) | Howard Aizenstein, Leonard Pitt |
| 1991 | Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices | Ilan Adler, Peter A. Beling |
| 1990 | General Weak Random Sources | David Zuckerman |
| 1990 | On ACC and Threshold Circuits | Andrew Chi-Chih Yao |
| 1990 | Randomized Online Graph Coloring (Preliminary Version) | Sundar Vishwanathan |
| 1990 | The Lattice Reduction Algorithm of Gauss: An Average Case Analysis | Brigitte Valle, Philippe Flajolet |
| 1990 | Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract) | Pravin M. Vaidya |
| 1990 | The Complexity of Finding Medians | Seinosuke Toda |
| 1990 | Efficiently Inverting Bijections Given by Straight Line Programs | Carl Sturtivant, Zhi-Li Zhang |
| 1990 | On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates | Roman Smolensky |
| 1990 | IP=PSPACE | Adi Shamir |
| 1990 | The Computability and Complexity of Optical Beam Tracing | John H. Reif, J. D. Tygar, Akitoshi Yoshida |