| 1989 | A Note on the Power of Threshold Circuits | Eric Allender |
| 1989 | Datalog vs. First-Order Logic | Mikls Ajtai, Yuri Gurevich |
| 1989 | Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract) | Yehuda Afek, Eli Gafni, Moty Ricklin |
| 1989 | On the Complexity of Fixed Parameter Problems (Extended Abstract) | Karl R. Abrahamson, John A. Ellis, Michael R. Fellows, Manuel E. Mata |
| 1989 | Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract) | Martn Abadi, Joseph Y. Halpern |
| 1988 | Near-Optimal Time-Space Tradeoff for Element Distinctness | Andrew Chi-Chih Yao |
| 1988 | New Algorithms for Finding Irreducible Polynomials over Finite Fields | Victor Shoup |
| 1988 | On the Complexity of omega-Automata | Shmuel Safra |
| 1988 | A Faster PSPACE Algorithm for Deciding the Existential Theory of the Reals | James Renegar |
| 1988 | Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract) | Franco P. Preparata, Roberto Tamassia |
| 1988 | New upper bounds in Klee's measure problem (extended abstract) | Mark H. Overmars, Chee-Keng Yap |
| 1988 | Fully Abstract Models of the Lazy Lambda Calculus | C.-H. Luke Ong |
| 1988 | Hardness vs. Randomness (Extended Abstract) | Noam Nisan, Avi Wigderson |
| 1988 | A Fast Planar Partition Algorithm, I (Extended Abstract) | Ketan Mulmuley |
| 1988 | Constructive Results from Graph Minors: Linkless Embeddings | Rajeev Motwani, Arvind Raghunathan, Huzur Saran |
| 1988 | Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time | Yoram Moses, Orli Waarts |
| 1988 | Nonexpressibility of Fairness and Signaling | David A. McAllester, Prakash Panangaden, Vasant Shanbhogue |
| 1988 | Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary) | Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1988 | Genus g Graphs have Pagenumber O(sqrt(g)) | Seth M. Malitz |
| 1988 | Removing Randomness in Parallel Computation Without a Processor Penalty | Michael Luby |
| 1988 | Lattices, Mbius Functions and Communication Complexity | Lszl Lovsz, Michael E. Saks |
| 1988 | Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract) | Nathan Linial, Yishay Mansour, Ronald L. Rivest |
| 1988 | Homogeneous Measures and Polynomial Time Invariants | Leonid A. Levin |
| 1988 | An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms | Frank Thomson Leighton, Satish Rao |
| 1988 | Universal Packet Routing Algorithms (Extended Abstract) | Frank Thomson Leighton, Bruce M. Maggs, Satish Rao |