| 1988 | A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract) Michael Ben-Or, Prasoon Tiwari |
| 1988 | A Faster Strongly Polynominal Minimum Cost Flow Algorithm James B. Orlin |
| 1988 | A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report) Joseph Y. Halpern, Yoram Moses, Mark R. Tuttle |
| 1988 | A Randomized Parallel Branch-and-Bound Procedure Richard M. Karp, Yanjun Zhang |
| 1988 | A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract) Danny Krizanc, David Peleg, Eli Upfal |
| 1988 | A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract) David Peleg, Eli Upfal |
| 1988 | Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems Harold N. Gabow, Robert Endre Tarjan |
| 1988 | Competitive Algorithms for On-line Problems Mark S. Manasse, Lyle A. McGeoch, Daniel Dominic Sleator |
| 1988 | Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract) Michael Ben-Or, Shafi Goldwasser, Avi Wigderson |
| 1988 | Computing Algebraic Formulas Using a Constant Number of Registers Michael Ben-Or, Richard Cleve |
| 1988 | Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) Mark Jerrum, Alistair Sinclair |
| 1988 | Decidable Optimization Problems for Database Logic Programs (Preliminary Report) Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi |
| 1988 | Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version) S. Rao Kosaraju, Gregory F. Sullivan |
| 1988 | Energy Consumption in VLSI Circuits (Preliminary Version) Alok Aggarwal, Ashok K. Chandra, Prabhakar Raghavan |
| 1988 | Errata to "How hard is to marry at random? (On the approximation of the permanent)". Andrei Z. Broder |
| 1988 | Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract) Mihalis Yannakakis |
| 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 | Founding Cryptography on Oblivious Transfer Joe Kilian |
| 1988 | Geometry Helps in Matching (Extended Abstract) Pravin M. Vaidya |
| 1988 | How to Sign Given Any Trapdoor Function (Extended Abstract) Mihir Bellare, Silvio Micali |
| 1988 | Implicit Representation of Graphs Sampath Kannan, Moni Naor, Steven Rudich |
| 1988 | Investigations of Fault-Tolerant Networks of Computers (Preliminary Version) Piotr Berman, Janos Simon |
| 1988 | Learning in the Presence of Malicious Errors (Extended Abstract) Michael J. Kearns, Ming Li |
| 1988 | Linearity and Unprovability of Set Union Problem Strategies Martin Loebl, Jaroslav Nesetril |
| 1988 | Lower Bounds on the Complexity of Graph Properties Valerie King |
| 1988 | Monotone Circuits for Connectivity Require Super-logarithmic Depth Mauricio Karchmer, Avi Wigderson |
| 1988 | More Analysis of Double Hashing George S. Lueker, Mariko Molodowitch |
| 1988 | Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson |
| 1988 | Multiparty Unconditionally Secure Protocols (Extended Abstract) David Chaum, Claude Crépeau, Ivan Damgård |
| 1988 | Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract) Manuel Blum, Paul Feldman, Silvio Micali |
| 1988 | Non-Oblivious Hashing (Extended Abstract) Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel |
| 1988 | Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space Yuri Gurevich, Saharon Shelah |
| 1988 | On Different Modes of Communication (Extended Abstract) Bernd Halstenberg, Rüdiger Reischuk |
| 1988 | On the Communication Complexity of Graph Properties András Hajnal, Wolfgang Maass, György Turán |
| 1988 | On the Power of White Pebbles (Extended Abstract) Bala Kalyanasundaram, Georg Schnitger |
| 1988 | Optimal Algorithms for Approximate Clustering Tomás Feder, Daniel H. Greene |
| 1988 | Optimal Algorithms for Byzantine Agreement 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 | Optimization, Approximation, and Complexity Classes (Extended Abstract) Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | Planning Constrained Motion Steven Fortune, Gordon T. Wilfong |
| 1988 | Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) Sorin Istrail |
| 1988 | Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA Janos Simon |
| 1988 | Random Instances of a Graph Coloring Problem Are Hard Ramarathnam Venkatesan, Leonid A. Levin |
| 1988 | Randomized Algorithms and Pseudorandom Numbers Howard J. Karloff, Prabhakar Raghavan |
| 1988 | Reasoning about Knowledge and Time in Asynchronous Systems Joseph Y. Halpern, Moshe Y. Vardi |
| 1988 | Relativized Polynominal Time Hierarchies Having Exactly K Levels Ker-I Ko |
| 1988 | Small Sets Supporting Fáry Embeddings of Planar Graphs Hubert de Fraysseix, János Pach, Richard Pollack |
| 1988 | Some Algebraic and Geometric Computations in PSPACE John F. Canny |
| 1988 | Storing and Searching a Multikey Table (Extended Abstract) Amos Fiat, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel |
| 1988 | Toward a Non-Atomic Era: \ell-Exclusion as a Test Case Danny Dolev, Eli Gafni, Nir Shavit |
| 1988 | Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | Two Infinite Sets of Primes with Fast Primality Tests Janos Pintz, William L. Steiger, Endre Szemerédi |
| 1988 | Using Smoothness to Achieve Parallelism (Abstract) Leonard M. Adleman, Kireeti Kompella |
| 1988 | Virtual Memory Algorithms (Preliminary Version) Alok Aggarwal, Ashok K. Chandra |