| 1987 | Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Brian Rogoff |
| 1987 | Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) | Johan Hstad, Frank Thomson Leighton, Mark Newman |
| 1987 | How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1987 | Towards a Theory of Software Protection and Simulation by Oblivious RAMs | Oded Goldreich |
| 1987 | Solving Minimum-Cost Flow Problems by Successive Approximation | Andrew V. Goldberg, Robert Endre Tarjan |
| 1987 | Parallel Symmetry-Breaking in Sparse Graphs | Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon |
| 1987 | The Power of Randomness for Communication Complexity (Preliminary Version) | Martin Frer |
| 1987 | A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract) | Greg N. Frederickson |
| 1987 | The Complexity of Perfect Zero-Knowledge (Extended Abstract) | Lance Fortnow |
| 1987 | Zero Knowledge Proofs of Identity | Uriel Feige, Amos Fiat, Adi Shamir |
| 1987 | Two Algorithms for Maintaining Order in a List | Paul F. Dietz, Daniel Dominic Sleator |
| 1987 | Matrix Multiplication via Arithmetic Progressions | Don Coppersmith, Shmuel Winograd |
| 1987 | Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract) | Kenneth L. Clarkson |
| 1987 | The Complexity of Cutting Convex Polytopes | Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas |
| 1987 | The Boolean Formula Value Problem Is in ALOGTIME | Samuel R. Buss |
| 1987 | An Optimal Online Algorithm for Metrical Task Systems | Allan Borodin, Nathan Linial, Michael E. Saks |
| 1987 | Size-Time Complexity of Boolean Networks for Prefix Computations | Gianfranco Bilardi, Franco P. Preparata |
| 1987 | Optimal Bounds for Decision Problems on the CRCW PRAM | Paul Beame, Johan Hstad |
| 1987 | Finite Monoids and the Fine Structure of NC¹ | David A. Mix Barrington, Denis Thrien |
| 1987 | Realistic Analysis of Some Randomized Algorithms | Eric Bach |
| 1987 | Permutation Groups in NC | Lszl Babai, Eugene M. Luks, kos Seress |
| 1987 | Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary) | Baruch Awerbuch |
| 1987 | Some Consequences of the Existence of Pseudorandom Generators | Eric Allender |
| 1987 | Deterministic Simulation in LOGSPACE | Mikls Ajtai, Jnos Komls, Endre Szemerdi |
| 1987 | A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon | Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, Peter W. Shor |