| 1988 | An Optimal Algorithm for Intersecting Line Segments in the Plane | Bernard Chazelle, Herbert Edelsbrunner |
| 1988 | On the Complexity of Kinodynamic Planning | John F. Canny, Bruce Randall Donald, John H. Reif, Patrick G. Xavier |
| 1988 | A Lower Bound for Matrix Multiplication | Nader H. Bshouty |
| 1988 | Bounds on the Cover Time (Preliminary Version) | Andrei Z. Broder, Anna R. Karlin |
| 1988 | On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract) | Lenore Blum, Mike Shub, Steve Smale |
| 1988 | Take a Walk, Grow a Tree (Preliminary Version) | Sandeep N. Bhatt, Jin-yi Cai |
| 1988 | On Pointers versus Addresses (Extended Abstract) | Amir M. Ben-Amram, Zvi Galil |
| 1988 | Fast Management of Permutation Groups | Lszl Babai, Eugene M. Luks, kos Seress |
| 1988 | Dynamic Networks Are as Fast as Static Networks (Preliminary Version) | Baruch Awerbuch, Michael Sipser |
| 1988 | On the Effects of Feedback in Dynamic Network Protocols (Preliminary Version) | Baruch Awerbuch |
| 1988 | Parallel Comparison Algorithms for Approximation Problems | Noga Alon, Yossi Azar |
| 1988 | Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) | Mikls Ajtai, Ronald Fagin |
| 1988 | The Complexity of the Pigeonhole Principle | Mikls Ajtai |
| 1988 | Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version) | Alok Aggarwal, James K. Park |
| 1987 | Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract) | Andrew Chi-Chih Yao |
| 1987 | Errata to "Atomic Shared Register Access by Asynchronous Hardware" | Paul M. B. Vitnyi, Baruch Awerbuch |
| 1987 | Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information | Martin Tompa, Heather Woll |
| 1987 | Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons" | Robert Endre Tarjan, Christopher J. Van Wyk |
| 1987 | Secret Linear Congruential Generators Are Not Cryptographically Secure | Jacques Stern |
| 1987 | Factoring Polynomials over Finite Fields | Lajos Rnyai |
| 1987 | Diversity-Based Inference of Finite Automata (Extended Abstract) | Ronald L. Rivest, Robert E. Schapire |
| 1987 | Finding Near Optimal Separators in Planar Graphs | Satish Rao |
| 1987 | How to emulate shared memory (Preliminary Version) | Abhiram G. Ranade |
| 1987 | Concurrent Reading While Writing II: The Multi-writer Case | Gary L. Peterson, James E. Burns |
| 1987 | Some Polynomial and Toeplitz Matrix Computations | Victor Y. Pan, John H. Reif |