| 1988 | Reasoning about Knowledge and Time in Asynchronous Systems | Joseph Y. Halpern, Moshe Y. Vardi |
| 1988 | A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report) | Joseph Y. Halpern, Yoram Moses, Mark R. Tuttle |
| 1988 | On the Communication Complexity of Graph Properties | Andrs Hajnal, Wolfgang Maass, Gyrgy Turn |
| 1988 | Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space | Yuri Gurevich, Saharon Shelah |
| 1988 | Finding Minimum-Cost Circulations by Canceling Negative Cycles | Andrew V. Goldberg, Robert Endre Tarjan |
| 1988 | Forests, Frames and Games: Algorithms for Matroid Sums and Applications | Harold N. Gabow, Herbert H. Westermann |
| 1988 | Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems | Harold N. Gabow, Robert Endre Tarjan |
| 1988 | Small Sets Supporting Fry Embeddings of Planar Graphs | Hubert de Fraysseix, Jnos Pach, Richard Pollack |
| 1988 | Planning Constrained Motion | Steven Fortune, Gordon T. Wilfong |
| 1988 | Storing and Searching a Multikey Table (Extended Abstract) | Amos Fiat, Moni Naor, Alejandro A. Schffer, Jeanette P. Schmidt, Alan Siegel |
| 1988 | Non-Oblivious Hashing (Extended Abstract) | Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel |
| 1988 | Optimal Algorithms for Byzantine Agreement | Paul Feldman, Silvio Micali |
| 1988 | Optimal Algorithms for Approximate Clustering | Toms Feder, Daniel H. Greene |
| 1988 | Toward a Non-Atomic Era: \ell-Exclusion as a Test Case | Danny Dolev, Eli Gafni, Nir Shavit |
| 1988 | Decidable Optimization Problems for Database Logic Programs (Preliminary Report) | Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi |
| 1988 | Multiparty Unconditionally Secure Protocols (Extended Abstract) | David Chaum, Claude Crpeau, Ivan Damgrd |
| 1988 | Some Algebraic and Geometric Computations in PSPACE | John F. Canny |
| 1988 | Errata to "How hard is to marry at random? (On the approximation of the permanent)". | Andrei Z. Broder |
| 1988 | Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract) | Manuel Blum, Paul Feldman, Silvio Micali |
| 1988 | Optimal Simulations by Butterfly Networks (Preliminary Version) | Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Arnold L. Rosenberg |
| 1988 | Investigations of Fault-Tolerant Networks of Computers (Preliminary Version) | Piotr Berman, Janos Simon |
| 1988 | A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract) | Michael Ben-Or, Prasoon Tiwari |
| 1988 | Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) | Michael Ben-Or, Shafi Goldwasser, Avi Wigderson |
| 1988 | Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions | Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson |
| 1988 | Computing Algebraic Formulas Using a Constant Number of Registers | Michael Ben-Or, Richard Cleve |