| 1989 | Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions | Bettina Just |
| 1989 | The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract) | Tao Jiang |
| 1989 | Space-efficient Static Trees and Graphs | Guy Jacobson |
| 1989 | Power of Fast VLSI Models Is Insensitive to Wires' Thinness | Gene Itkis, Leonid A. Levin |
| 1989 | How to Recycle Random Bits | Russell Impagliazzo, David Zuckerman |
| 1989 | Decision Versus Search Problems in Super-Polynomial Time | Russell Impagliazzo, Gbor Tardos |
| 1989 | Efficient Cryptographic Schemes Provably as Secure as Subset Sum | Russell Impagliazzo, Moni Naor |
| 1989 | One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract) | Russell Impagliazzo, Michael Luby |
| 1989 | Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version) | Kieran T. Herley |
| 1989 | Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results | David Haussler |
| 1989 | Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract) | Mark D. Hansen |
| 1989 | Approximation Schemes for Constrained Scheduling Problems | Leslie A. Hall, David B. Shmoys |
| 1989 | Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version) | Michael T. Goodrich, S. Rao Kosaraju |
| 1989 | Learning Binary Relations and Total Orders (Extended Abstract) | Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire |
| 1989 | Interior-Point Methods in Parallel Computation | Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, va Tardos |
| 1989 | Testing Permutation Polynomials (Extended Abstract) | Joachim von zur Gathen |
| 1989 | Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids | Harold N. Gabow, Ying Xu |
| 1989 | Ensemble Motion Planning in Trees | Greg N. Frederickson, D. J. Guan |
| 1989 | Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version) | Greg N. Frederickson |
| 1989 | Stable Maintenance of Point Set Triangulations in Two Dimensions | Steven Fortune |
| 1989 | Planning and Learning in Permutation Groups | Amos Fiat, Shahar Moses, Adi Shamir, Ilan Shimshoni, Gbor Tardos |
| 1989 | Every Polynomial-Time 1-Degree Collapses iff P=PSPACE | Stephen A. Fenner, Stuart A. Kurtz, James S. Royer |
| 1989 | An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract) | Michael R. Fellows, Michael A. Langston |
| 1989 | On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract) | Cynthia Dwork, Larry J. Stockmeyer |
| 1989 | Asymptotically Fast Algorithms for Spherical and Related Transforms | James R. Driscoll, Dennis M. Healy Jr. |