| 1987 | Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version) | Pavol Duris, Zvi Galil |
| 1987 | Delaunay Graphs are Almost as Good as Complete Graphs | David P. Dobkin, Steven J. Friedman, Kenneth J. Supowit |
| 1987 | Database Theory and Cylindric Lattices (Extended Abstract) | Stavros S. Cosmadakis |
| 1987 | Parallel Graph Algorithms that Are Efficient on Average | Don Coppersmith, Prabhakar Raghavan, Martin Tompa |
| 1987 | Polytope Range Searching and Integral Geometry (Extended Abstract) | Bernard Chazelle |
| 1987 | New Lower Bound Techniques for Robot Motion Planning Problems | John F. Canny, John H. Reif |
| 1987 | A New Algebraic Method for Robot Motion Planning and Real Geometry | John F. Canny |
| 1987 | On the Second Eigenvalue of Random Regular Graphs (Preliminary Version) | Andrei Z. Broder, Eli Shamir |
| 1987 | Eigenvalues and Graph Bisection: An Average-Case Analysis (Extended Abstract) | Ravi B. Boppana |
| 1987 | Generic Oracles and Oracle Classes (Extended Abstract) | Manuel Blum, Russell Impagliazzo |
| 1987 | Learning One-Counter Languages in Polynomial Time (Extended Abstract) | Piotr Berman, Robert Roos |
| 1987 | Achievable Cases in an Asynchronous Environment (Extended Abstract) | Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Daphne Koller, David Peleg, Rdiger Reischuk |
| 1987 | Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms | Mikhail J. Atallah, Richard Cole, Michael T. Goodrich |
| 1987 | The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms | Noga Alon, Yossi Azar |
| 1987 | Recursive Construction for 3-Regular Expanders | Mikls Ajtai |
| 1987 | Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds | William Aiello, Johan Hstad |
| 1987 | Hierarchical Memory with Block Transfer | Alok Aggarwal, Ashok K. Chandra, Marc Snir |
| 1987 | Local Management of a Global Resource in a Communication Network | Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks |
| 1987 | Applying Static Network Protocols to Dynamic Networks | Yehuda Afek, Baruch Awerbuch, Eli Gafni |
| 1986 | How to Generate and Exchange Secrets (Extended Abstract) | Andrew Chi-Chih Yao |
| 1986 | Lower Bounds for Accessing Binary Search Trees With Rotations (Preliminary Version) | Robert E. Wilber |
| 1986 | Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments | Ady Wiernik |
| 1986 | Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract) | Paul M. B. Vitnyi, Baruch Awerbuch |
| 1986 | A New Pebble Game that Characterizes Parallel Complexity Classes | H. Venkateswaran, Martin Tompa |
| 1986 | An optimal algorithm for the All-Nearest-Neighbors Problem | Pravin M. Vaidya |