| 1990 | Uniform Memory Hierarchies | Bowen Alpern, Larry Carter, Ephraim Feig |
| 1990 | Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract) | Noga Alon, Moni Naor |
| 1990 | Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time | Noga Alon, Nimrod Megiddo |
| 1990 | Simple Constructions of Almost k-Wise Independent Random Variables | Noga Alon, Oded Goldreich, Johan Hstad, Ren Peralta |
| 1990 | A Markovian Extension of Valiant's Learning Model (Extended Abstract) | David J. Aldous, Umesh V. Vazirani |
| 1990 | A Time-Space Tradeoff for Boolean Matrix Multiplication | Karl R. Abrahamson |
| 1989 | Lower Bounds for Algebraic Computation Trees with Integer Inputs | Andrew Chi-Chih Yao |
| 1989 | A New Algorithm for Minimizing Convex Functions over Convex Sets (Extended Abstract) | Pravin M. Vaidya |
| 1989 | Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract) | Pravin M. Vaidya |
| 1989 | The Equivalence and Learning of Probabilistic Automata (Extended Abstract) | Wen-Guey Tzeng |
| 1989 | On the Computational Power of PP and +P | Seinosuke Toda |
| 1989 | Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem | Rajamani Sundar |
| 1989 | On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract) | Alan Siegel |
| 1989 | The Strength of Weak Learnability (Extended Abstract) | Robert E. Schapire |
| 1989 | Full Abstraction for Nondeterministic Dataflow Networks | James R. Russell |
| 1989 | Galois Groups and Factoring Polynomials over Finite Fields | Lajos Rnyai |
| 1989 | Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) | Ran Raz, Avi Wigderson |
| 1989 | An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract) | Vijaya Ramachandran, John H. Reif |
| 1989 | On the Network Complexity of Selection | C. Greg Plaxton |
| 1989 | An Upper Bound on the Number of Planar k-Sets | Jnos Pach, William L. Steiger, Endre Szemerdi |
| 1989 | The 0-1 Law Fails for the Class of Existential Second Order Gdel Sentences with Equality | Leszek Pacholski, Wieslaw Szwast |
| 1989 | Output-Sensitive Hidden Surface Removal | Mark H. Overmars, Micha Sharir |
| 1989 | Lower Bounds for the Stable Marriage Problem and its Variants | Cheng Ng |
| 1989 | On Obstructions in Relation to a Fixed Viewpoint | Ketan Mulmuley |
| 1989 | The Probabilistic Method Yields Deterministic Parallel Algorithms | Rajeev Motwani, Joseph Naor, Moni Naor |