| 1989 | A General Sequential Time-Space Tradeoff for Finding Unique Elements Paul Beame |
| 1989 | A Hard-Core Predicate for all One-Way Functions Oded Goldreich, Leonid A. Levin |
| 1989 | A New Fixed Point Approach for Stable Networks and Stable Marriages Tomás Feder |
| 1989 | A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies Martin E. Dyer, Alan M. Frieze, Ravi Kannan |
| 1989 | A Zero-One Law for Boolean Privacy (extended abstract) Benny Chor, Eyal Kushilevitz |
| 1989 | An O(log N) Deterministic Packet Routing Scheme (Preliminary Version) Eli Upfal |
| 1989 | An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring) Avrim Blum |
| 1989 | Bounded Concurrent Time-Stamp Systems Are Constructible Danny Dolev, Nir Shavit |
| 1989 | CREW PRAMs and Decision Trees Noam Nisan |
| 1989 | Circuits and Local Computation Andrew Chi-Chih Yao |
| 1989 | Compact Distributed Data Structures for Adaptive Routing (Extended Abstract) Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1989 | Coordinate Representation of Order Types Requires Exponential Storage Jacob E. Goodman, Richard Pollack, Bernd Sturmfels |
| 1989 | Cryptographic Limitations on Learning Boolean Formulae and Finite Automata Michael J. Kearns, Leslie G. Valiant |
| 1989 | Designing Programs That Check Their Work Manuel Blum, Sampath Kannan |
| 1989 | Distributed Shortest Paths Algorithms (Extended Abstract) Baruch Awerbuch |
| 1989 | Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems Rajeev Motwani |
| 1989 | Expressiveness of Restricted Recursive Queries (Extended Abstract) Foto N. Afrati, Stavros S. Cosmadakis |
| 1989 | Fast Computation Using Faulty Hypercubes (Extended Abstract) Johan Håstad, Frank Thomson Leighton, Mark Newman |
| 1989 | Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) Stephen A. Cook, Alasdair Urquhart |
| 1989 | Highly Parallelizable Problems (Extended Abstract) Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin |
| 1989 | Implicit O(1) Probe Search Amos Fiat, Moni Naor |
| 1989 | Inference of Finite Automata Using Homing Sequences (Extended Abstract) Ronald L. Rivest, Robert E. Schapire |
| 1989 | Limits on the Provable Consequences of One-Way Permutations Russell Impagliazzo, Steven Rudich |
| 1989 | Lines in Space-Combinatorics, Algorithms and Applications Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir |
| 1989 | Local Reorientation, Global Order, and Planar Topology (Preliminary Version) Ming-Yang Kao, Gregory E. Shannon |
| 1989 | Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract) Allan Borodin, Walter L. Ruzzo, Martin Tompa |
| 1989 | Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) László Babai, Noam Nisan, Mario Szegedy |
| 1989 | On Aspects of Universality and Performance for Closed Hashing (Extended Abstract) Jeanette P. Schmidt, Alan Siegel |
| 1989 | On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract) Michael R. Fellows, Michael A. Langston |
| 1989 | On omega-Automata and Temporal Logic (Preliminary Report) Shmuel Safra, Moshe Y. Vardi |
| 1989 | On the Complexity of Radio Communication (Extended Abstract) Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1989 | On the Extended Direct Sum Conjecture Nader H. Bshouty |
| 1989 | On the Improbability of Reaching Byzantine Agreements (Preliminary Version) Ronald L. Graham, Andrew Chi-Chih Yao |
| 1989 | On the Method of Approximations Alexander A. Razborov |
| 1989 | On the Second Eigenvalue in Random Regular Graphs Joel Friedman, Jeff Kahn, Endre Szemerédi |
| 1989 | On the Theory of Average Case Complexity Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby |
| 1989 | Optimal Separations Between Concurrent-Write Parallel Machines Ravi B. Boppana |
| 1989 | Optimal Size Integer Division Circuits John H. Reif, Stephen R. Tate |
| 1989 | Parallel Depth-First Search in General Directed Graphs (Preliminary Version) Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao |
| 1989 | Polling: A New Randomized Sampling Technique for Computational Geometry John H. Reif, Sandeep Sen |
| 1989 | Probabilistic Computation and Linear Time |
| 1989 | Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA David S. Johnson |
| 1989 | Proof of a Conjecture of R. Kannan Jean-Camille Birget |
| 1989 | Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues Brigitte Vallée |
| 1989 | Pseudo-random Generation from one-way functions (Extended Abstracts) Russell Impagliazzo, Leonid A. Levin, Michael Luby |
| 1989 | Quantifier Elimination in the Theory of an Algebraically-closed Field Doug Ierardi |
| 1989 | Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version) Edith Cohen, Nimrod Megiddo |
| 1989 | The Cell Probe Complexity of Dynamic Data Structures Michael L. Fredman, Michael E. Saks |
| 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 | The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract) Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer |
| 1989 | The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial Leonard Pitt, Manfred K. Warmuth |
| 1989 | Tradeoffs Between Communication and Space Tak Wah Lam, Prasoon Tiwari, Martin Tompa |
| 1989 | Trading Space for Time in Undirected s-t Connectivity Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal |
| 1989 | Universal One-Way Hash Functions and their Cryptographic Applications Moni Naor, Moti Yung |
| 1989 | Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract) Tal Rabin, Michael Ben-Or |
| 1989 | Verifying Partial Orders Claire Kenyon-Mathieu, Valerie King |
| 1989 | Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract) Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg |