| 1989 | Optimal Size Integer Division Circuits | John H. Reif, Stephen R. Tate |
| 1989 | Polling: A New Randomized Sampling Technique for Computational Geometry | John H. Reif, Sandeep Sen |
| 1989 | On the Method of Approximations | Alexander A. Razborov |
| 1989 | Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract) | Tal Rabin, Michael Ben-Or |
| 1989 | The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial | Leonard Pitt, Manfred K. Warmuth |
| 1989 | CREW PRAMs and Decision Trees | Noam Nisan |
| 1989 | Universal One-Way Hash Functions and their Cryptographic Applications | Moni Naor, Moti Yung |
| 1989 | Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems | Rajeev Motwani |
| 1989 | Tradeoffs Between Communication and Space | Tak Wah Lam, Prasoon Tiwari, Martin Tompa |
| 1989 | The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract) | Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer |
| 1989 | Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract) | Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg |
| 1989 | Verifying Partial Orders | Claire Kenyon-Mathieu, Valerie King |
| 1989 | Cryptographic Limitations on Learning Boolean Formulae and Finite Automata | Michael J. Kearns, Leslie G. Valiant |
| 1989 | Local Reorientation, Global Order, and Planar Topology (Preliminary Version) | Ming-Yang Kao, Gregory E. Shannon |
| 1989 | Limits on the Provable Consequences of One-Way Permutations | Russell Impagliazzo, Steven Rudich |
| 1989 | Pseudo-random Generation from one-way functions (Extended Abstracts) | Russell Impagliazzo, Leonid A. Levin, Michael Luby |
| 1989 | Quantifier Elimination in the Theory of an Algebraically-closed Field | Doug Ierardi |
| 1989 | Fast Computation Using Faulty Hypercubes (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Mark Newman |
| 1989 | On the Improbability of Reaching Byzantine Agreements (Preliminary Version) | Ronald L. Graham, Andrew Chi-Chih Yao |
| 1989 | Coordinate Representation of Order Types Requires Exponential Storage | Jacob E. Goodman, Richard Pollack, Bernd Sturmfels |
| 1989 | A Hard-Core Predicate for all One-Way Functions | Oded Goldreich, Leonid A. Levin |
| 1989 | On the Second Eigenvalue in Random Regular Graphs | Joel Friedman, Jeff Kahn, Endre Szemerdi |
| 1989 | The Cell Probe Complexity of Dynamic Data Structures | Michael L. Fredman, Michael E. Saks |
| 1989 | Probabilistic Computation and Linear Time | |
| 1989 | Implicit O(1) Probe Search | Amos Fiat, Moni Naor |