| 1992 | Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths | Mikls Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerdi |
| 1992 | Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries | Howard Aizenstein, Lisa Hellerstein, Leonard Pitt |
| 1992 | Efficient Minimum Cost Matching Using Quadrangle Inequality | Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber |
| 1992 | Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees | Pankaj K. Agarwal, David Eppstein, Jir Matousek |
| 1991 | Simulating BPP Using a General Weak Random Source | David Zuckerman |
| 1991 | Communication Complexity for Parallel Divide-and-Conquer | I-Chen Wu, H. T. Kung |
| 1991 | An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton | Weiguo Wang |
| 1991 | Optimal Prefetching via Data Compression (Extended Abstract) | Jeffrey Scott Vitter, P. Krishnan |
| 1991 | A Theory of Using History for Equational Systems with Applications (Extended Abstract) | Rakesh M. Verma |
| 1991 | A Lower Bound for the Dictionary Problem under a Hashing Model | Rajamani Sundar |
| 1991 | Lower Bounds for Polynomial Evaluation and Interpolation Problems | Victor Shoup, Roman Smolensky |
| 1991 | How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing | Peter W. Shor |
| 1991 | Scheduling Parallel Machines On-Line | David B. Shmoys, Joel Wein, David P. Williamson |
| 1991 | Dynamic Maintenance of Geometric Structures Made Easy | Otfried Schwarzkopf |
| 1991 | Finding k-cuts within Twice the Optimal | Huzur Saran, Vijay V. Vazirani |
| 1991 | Reliable Computation with Noisy Circuits and Decision Trees-A General n log n Lower Bound | Rdiger Reischuk, Bernd Schmeltz |
| 1991 | Better Bounds for Threshold Formulas | Jaikumar Radhakrishnan |
| 1991 | Fast Approximation Algorithms for Fractional Packing and Covering Problems | Serge A. Plotkin, David B. Shmoys, va Tardos |
| 1991 | Shrinkage of de~Morgan formulae under restriction | Mike Paterson, Uri Zwick |
| 1991 | On Selecting a Satisfying Truth Assignment (Extended Abstract) | Christos H. Papadimitriou |
| 1991 | Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity | Alon Orlitsky |
| 1991 | Optimal File Sharing in Distributed Networks (Preliminary Version) | Moni Naor, Ron M. Roth |
| 1991 | Randomized Multidimensional Search Trees: Further Results in Dynamic Sampling (Extended Abstract) | Ketan Mulmuley |
| 1991 | Randomized Multidimensional Search Trees: Lazy Balancing and Dynamic Shuffling (Extended Abstract) | Ketan Mulmuley |
| 1991 | Explicit Construction of Natural Bounded Concentrators | Moshe Morgenstern |