| 1989 | On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract) | Michael R. Fellows, Michael A. Langston |
| 1989 | A New Fixed Point Approach for Stable Networks and Stable Marriages | Toms Feder |
| 1989 | A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies | Martin E. Dyer, Alan M. Frieze, Ravi Kannan |
| 1989 | Bounded Concurrent Time-Stamp Systems Are Constructible | Danny Dolev, Nir Shavit |
| 1989 | Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) | Stephen A. Cook, Alasdair Urquhart |
| 1989 | Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version) | Edith Cohen, Nimrod Megiddo |
| 1989 | A Zero-One Law for Boolean Privacy (extended abstract) | Benny Chor, Eyal Kushilevitz |
| 1989 | Lines in Space-Combinatorics, Algorithms and Applications | Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir |
| 1989 | The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract) | Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari |
| 1989 | On the Extended Direct Sum Conjecture | Nader H. Bshouty |
| 1989 | Trading Space for Time in Undirected s-t Connectivity | Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal |
| 1989 | Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract) | Allan Borodin, Walter L. Ruzzo, Martin Tompa |
| 1989 | Optimal Separations Between Concurrent-Write Parallel Machines | Ravi B. Boppana |
| 1989 | Designing Programs That Check Their Work | Manuel Blum, Sampath Kannan |
| 1989 | An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring) | Avrim Blum |
| 1989 | Proof of a Conjecture of R. Kannan | Jean-Camille Birget |
| 1989 | Highly Parallelizable Problems (Extended Abstract) | Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin |
| 1989 | On the Theory of Average Case Complexity | Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby |
| 1989 | A General Sequential Time-Space Tradeoff for Finding Unique Elements | Paul Beame |
| 1989 | Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) | Lszl Babai, Noam Nisan, Mario Szegedy |
| 1989 | Compact Distributed Data Structures for Adaptive Routing (Extended Abstract) | Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1989 | Distributed Shortest Paths Algorithms (Extended Abstract) | Baruch Awerbuch |
| 1989 | On the Complexity of Radio Communication (Extended Abstract) | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1989 | Parallel Depth-First Search in General Directed Graphs (Preliminary Version) | Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao |
| 1989 | Expressiveness of Restricted Recursive Queries (Extended Abstract) | Foto N. Afrati, Stavros S. Cosmadakis |