| 1992 | Ray Shooting and Parametric Search | Pankaj K. Agarwal, Jir Matousek |
| 1992 | Polynomial Algorithms for Linear Programming over the Algebraic Numbers | Ilan Adler, Peter A. Beling |
| 1991 | Testing Finite State Machines (Extended Abstract) | Mihalis Yannakakis, David Lee |
| 1991 | Separating Concurrent Languages with Categories of Language Embeddings (Extended Abstract) | Ehud Shapiro |
| 1991 | Rounds in Communication Complexity Revisited | Noam Nisan, Avi Wigderson |
| 1991 | Lower Bounds for Non-Commutative Computation (Extended Abstract) | Noam Nisan |
| 1991 | Hidden Surface Removal with Respect to a Moving View Point | Ketan Mulmuley |
| 1991 | Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field | Alfred Menezes, Scott A. Vanstone, Tatsuaki Okamoto |
| 1991 | Perfect Cryptographic Security from Partially Independent Channels | Ueli M. Maurer |
| 1991 | Approximations and Optimal Geometric Divide-And-Conquer | Jir Matousek |
| 1991 | Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (Extended Abstract) | Yossi Matias, Uzi Vishkin |
| 1991 | On Deterministic Approximation of DNF | Michael Luby, Boban Velickovic |
| 1991 | On-Line Learning of Linear Functions | Nick Littlestone, Philip M. Long, Manfred K. Warmuth |
| 1991 | Fast Approximation Algorithms for Multicommodity Flow Problems | Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, va Tardos, Spyros Tragoudas |
| 1991 | Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract) | Eyal Kushilevitz, Yishay Mansour |
| 1991 | Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (Extended Abstract) | Ker-I Ko |
| 1991 | A General Completeness Theorem for Two-Party Games | Joe Kilian |
| 1991 | Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing (Extended Abstract) | Zvi M. Kedem, Krishna V. Palem, A. Raghunathan, Paul G. Spirakis |
| 1991 | Probabilistic Recurrence Relations | Richard M. Karp |
| 1991 | Lower Bounds for Randomized k-Server and Motion Planning Algorithms | Howard J. Karloff, Yuval Rabani, Yiftach Ravid |
| 1991 | Effective Noether Irreducibility Forms and Applications (Extended Abstract) | Erich L. Kaltofen |
| 1991 | A Model for Data in Motion | Simon Kahan |
| 1991 | Hamiltonian Paths in Infinite Graphs | David Harel |
| 1991 | Constant-Time Parallel Integer Sorting (Extended Abstract) | Torben Hagerup |
| 1991 | The Harmonic Online K-Server Algorithm Is Competitive | Edward F. Grove |