| 1989 | Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract) | Gary L. Miller, Joseph Naor |
| 1989 | Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic | Victor Milenkovic |
| 1989 | Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders | Milena Mihail |
| 1989 | On the Complexity of a Game Related to the Dictionary Problem | Kurt Mehlhorn, Stefan Nher, Monika Rauch |
| 1989 | Fast Matching Algorithms for Points on a Polygon (Extended Abstract) | Odile Marcotte, Subhash Suri |
| 1989 | The Complexity of Approximating the Square Root (Extended Summary) | Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1989 | On the Complexity of Learning From Counterexamples (Extended Abstract) | Wolfgang Maass, Gyrgy Turn |
| 1989 | A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract) | Ming Li, Paul M. B. Vitnyi |
| 1989 | The Weighted Majority Algorithm | Nick Littlestone, Manfred K. Warmuth |
| 1989 | On Reversal Complexity for Alternating Turing Machines (Extended Abstract) | Maciej Liskiewicz, Krzysztof Lorys |
| 1989 | Graph Products and Chromatic Numbers | Nathan Linial, Umesh V. Vazirani |
| 1989 | Constant Depth Circuits, Fourier Transform, and Learnability | Nathan Linial, Yishay Mansour, Noam Nisan |
| 1989 | Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies | Frank Thomson Leighton, Bruce M. Maggs |
| 1989 | Simplification of Nested Radicals | Susan Landau |
| 1989 | Privacy and Communication Complexity | Eyal Kushilevitz |
| 1989 | Area-Optimal Three-Layer Channel Routing | Ruth Kuchem, Dorothea Wagner, Frank Wagner |
| 1989 | Structure in Locally Optimal Solutions (Extended Abstract) | Mark W. Krentel |
| 1989 | Pipelining Computations in a Tree of Processors (Preliminary Version) | S. Rao Kosaraju |
| 1989 | Efficient Tree Pattern Matching (Preliminary Version) | S. Rao Kosaraju |
| 1989 | Computational Complexity of Roots of Real Functions (Extended Abstract) | Ker-I Ko |
| 1989 | The Parallel Complexity of the Subgraph Connectivity Problem | Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis |
| 1989 | Minimum Resource Zero-Knowledge Proofs (Extended Abstract) | Joe Kilian, Silvio Micali, Rafail Ostrovsky |
| 1989 | Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary) | Samir Khuller, Baruch Schieber |
| 1989 | Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph | Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani |
| 1989 | Lower Bounds for Pseudorandom Number Generators | Michael Kharitonov, Andrew V. Goldberg, Moti Yung |