| 1987 | A Model for Hierarchical Memory | Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, Marc Snir |
| 1987 | A Random NC Algorithm for Depth First Search | Alok Aggarwal, Richard J. Anderson |
| 1987 | Recognizing Primes in Random Polynomial Time | Leonard M. Adleman, Ming-Deh A. Huang |
| 1987 | On Hiding Information from an Oracle (Extended Abstract) | Martn Abadi, Joan Feigenbaum, Joe Kilian |
| 1986 | Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract) | Mihalis Yannakakis |
| 1986 | A Linear-Time Algorithm for Triangulating Simple Polygons | Robert Endre Tarjan, Christopher J. Van Wyk |
| 1986 | Rotation Distance, Triangulations, and Hyperbolic Geometry | Daniel Dominic Sleator, Robert Endre Tarjan, William P. Thurston |
| 1986 | Aspects of Information Flow in VLSI Circuits (Extended Abstract) | Alan Siegel |
| 1986 | Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face | Raimund Seidel |
| 1986 | An Optimal Sorting Algorithm for Mesh Connected Computers | Claus-Peter Schnorr, Adi Shamir |
| 1986 | A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field | Ketan Mulmuley |
| 1986 | Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version) | George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran |
| 1986 | Pseudo-random Permutation Generators and Cryptographic Composition | Michael Luby, Charles Rackoff |
| 1986 | Explicit Expanders and the Ramanujan Conjectures | Alexander Lubotzky, Ralph Phillips, Peter Sarnak |
| 1986 | New Lower Bounds for Parallel Computation | Ming Li, Yaacov Yesha |
| 1986 | Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms | Frank Thomson Leighton, Peter W. Shor |
| 1986 | Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm | Gad M. Landau, Uzi Vishkin |
| 1986 | The Complexity of Optimization Problems | Mark W. Krentel |
| 1986 | Optimal Simulations between Mesh-Connected Arrays of Processors (Preliminary Version) | S. Rao Kosaraju, Mikhail J. Atallah |
| 1986 | Parallel Evaluation of Division-Free Arithmetic Expressions | S. Rao Kosaraju |
| 1986 | A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract) | Ker-I Ko, Timothy J. Long, Ding-Zhu Du |
| 1986 | Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version) | Anna R. Karlin, Eli Upfal |
| 1986 | Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows | Sanjiv Kapoor, Pravin M. Vaidya |
| 1986 | Uniform Closure Properties of P-Computable Functions | Erich L. Kaltofen |
| 1986 | Almost Optimal Lower Bounds for Small Depth Circuits | Johan Hstad |