| 1989 | Multiparty Communication Complexity | Danny Dolev, Toms Feder |
| 1989 | Dynamically Computing the Maxima of Decomposable Functions, with Applications | David P. Dobkin, Subhash Suri |
| 1989 | The Inverse of an Automorphism in Polynomial Time | Matthew Dickerson |
| 1989 | An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) | Elias Dahlhaus, Marek Karpinski |
| 1989 | Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract) | Stephen A. Cook, Bruce M. Kapron |
| 1989 | On the Complexity of Space Bounded Interactive Proofs (Extended Abstract) | Anne Condon, Richard J. Lipton |
| 1989 | Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) | Aviad Cohen, Avi Wigderson |
| 1989 | Solvability in Asynchronous Environments (Extended Abstract) | Benny Chor, Lior Moscovici |
| 1989 | A Randomized Maximum-Flow Algorithm | Joseph Cheriyan, Torben Hagerup |
| 1989 | An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract) | Bernard Chazelle |
| 1989 | Subquadratic Simulations of Circuits by Branching Programs | Jin-yi Cai, Richard J. Lipton |
| 1989 | An Optimal Lower Bound on the Number of Variables for Graph Identification | Jin-yi Cai, Martin Frer, Neil Immerman |
| 1989 | Lower Bounds for Constant Depth Circuits in the Presence of Help Bits | Jin-yi Cai |
| 1989 | Generating Random Spanning Trees | Andrei Z. Broder |
| 1989 | Towards Optimal Distributed Consensus (Extended Abstract) | Piotr Berman, Juan A. Garay, Kenneth J. Perry |
| 1989 | Recursive *-Tree Parallel Data-Structure (Extended Abstract) | Omer Berkman, Uzi Vishkin |
| 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry | Bonnie Berger, John Rompel, Peter W. Shor |
| 1989 | Simulating (log ^c n)-wise Independence in NC | Bonnie Berger, John Rompel |
| 1989 | Multiparty Computation with Faulty Majority (Extended Announcement) | Donald Beaver, Shafi Goldwasser |
| 1989 | Incremental Planarity Testing (Extended Abstract) | Giuseppe Di Battista, Roberto Tamassia |
| 1989 | Computing Irreducible Representations of Finite Groups | Lszl Babai, Lajos Rnyai |
| 1989 | Polynomial End-To-End Communication (Extended Abstract) | Baruch Awerbuch, Yishay Mansour, Nir Shavit |
| 1989 | Network Decomposition and Locality in Distributed Computation | Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin |
| 1989 | Randomized Search Trees | Cecilia R. Aragon, Raimund Seidel |
| 1989 | A Really Temporal Logic | Rajeev Alur, Thomas A. Henzinger |