| 1989 | The Complexity of Nonlinear Separable Optimization. | Dorit S. Hochbaum, J. George Shanthikumar |
| 1989 | Tensor Rank is NP-Complete. | Johan Hstad |
| 1989 | Parallel Retrieval of Scattered Information. | Torben Hagerup, Manfred Nowak |
| 1989 | Structural Operational Semantics and Bisimulation as a Congruence (Extended Abstract). | Jan Friso Groote, Frits W. Vaandrager |
| 1989 | A Pointer-Free Data Structure for Merging Heaps and Min-Max Heaps. | Giorgio Gambosi, Enrico Nardelli, Maurizio Talamo |
| 1989 | An Improved Algorithm for Approximate String Matching. | Zvi Galil, Kunsoo Park |
| 1989 | Finding Triconnected Components by Local Replacements. | Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella |
| 1989 | An Optimal Probabilistic Algorithm For Synchronous Byzantine Agreement. | Paul Feldman, Silvio Micali |
| 1989 | On Dice and Coins: Models of Computation for Random Generation. | David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir |
| 1989 | Parallel Algorithmic Techniques for Combinatorial Computation. | David Eppstein, Zvi Galil |
| 1989 | Automata with Storage on Infinite Words. | Joost Engelfriet, Hendrik Jan Hoogeboom |
| 1989 | On Recent Trends in Algebraic Specification. | Hartmut Ehrig, Peter Pepper, Fernando Orejas |
| 1989 | Infinite Normal Forms (Preliminary Version). | Nachum Dershowitz, Stphane Kaplan, David A. Plaisted |
| 1989 | Causal Trees. | Philippe Darondeau, Pierpaolo Degano |
| 1989 | Dominoes and the Regularity of DNS Splicing Languages. | Karel Culk II, Tero Harju |
| 1989 | The Definability of Equational Graphs in Monadic Second-Order Logic. | Bruno Courcelle |
| 1989 | About Primitive Recursive Algorithms. | Loc Colson |
| 1989 | A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications. | Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir |
| 1989 | Relational Semantics for Recursive Types and Bounded Quantification. | Felice Cardone |
| 1989 | Completion of Finite Codes with Finite Deciphering Delay. | Vronique Bruyre |
| 1989 | Everything in NP can be Argued in Perfect Zero-Knowledge in a Bounded Number of Rounds. | Gilles Brassard, Claude Crpeau, Moti Yung |
| 1989 | Subduing Self-Application. | Corrado Bhm |
| 1989 | Time Lower Bounds For CREW-PRAM Computation Of Monotone Functions. | Gianfranco Bilardi, Abha Moitra |
| 1989 | Asymptotically Optimal Distributed Consensus (Extended Abstract). | Piotr Berman, Juan A. Garay |
| 1989 | Factors of Words. | Danile Beauquier, Jean-Eric Pin |