| 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 |
| 1987 | A Model for Hierarchical Memory Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, Marc Snir |
| 1987 | A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract) Greg N. Frederickson |
| 1987 | A New Graph Triconnectivity Algorithm and Its Parallelization Gary L. Miller, Vijaya Ramachandran |
| 1987 | A Random NC Algorithm for Depth First Search Alok Aggarwal, Richard J. Anderson |
| 1987 | Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity Roman Smolensky |
| 1987 | An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations Pravin M. Vaidya |
| 1987 | An Optimal Online Algorithm for Metrical Task Systems Allan Borodin, Nathan Linial, Michael E. Saks |
| 1987 | Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) Johan Håstad, Frank Thomson Leighton, Brian Rogoff |
| 1987 | Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract) Kenneth L. Clarkson |
| 1987 | Constructing Disjoint Paths on Expander Graphs (Extended Abstract) David Peleg, Eli Upfal |
| 1987 | Deterministic Simulation in LOGSPACE Miklós Ajtai, János Komlós, Endre Szemerédi |
| 1987 | Dynamic Parallel Complexity of Computational Circuits Gary L. Miller, Shang-Hua Teng |
| 1987 | Efficiency Considerations in Using Semi-random Sources (Extended Abstract) Umesh V. Vazirani |
| 1987 | Fast Parallel Algorithms for Chordal Graphs (Extended Abstract) Joseph Naor, Moni Naor, Alejandro A. Schäffer |
| 1987 | Finite Monoids and the Fine Structure of NC¹ David A. Mix Barrington, Denis Thérien |
| 1987 | How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1987 | Imperfect Random Sources and Discrete Controlled Processes David Lichtenstein, Nathan Linial, Michael E. Saks |
| 1987 | Matching Is as Easy as Matrix Inversion Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani |
| 1987 | Matrix Multiplication via Arithmetic Progressions Don Coppersmith, Shmuel Winograd |
| 1987 | On Hiding Information from an Oracle (Extended Abstract) Martín Abadi, Joan Feigenbaum, Joe Kilian |
| 1987 | On Learning Boolean Functions B. K. Natarajan |
| 1987 | On the Learnability of Boolean Formulae Michael J. Kearns, Ming Li, Leonard Pitt, Leslie G. Valiant |
| 1987 | Optimal Bounds for Decision Problems on the CRCW PRAM Paul Beame, Johan Håstad |
| 1987 | Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary) Baruch Awerbuch |
| 1987 | Parallel Symmetry-Breaking in Sparse Graphs Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon |
| 1987 | Permutation Groups in NC László Babai, Eugene M. Luks, Ákos Seress |
| 1987 | Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA Alfred V. Aho |
| 1987 | Properties that Characterize LOGCFL H. Venkateswaran |
| 1987 | Realistic Analysis of Some Randomized Algorithms Eric Bach |
| 1987 | Recognizing Primes in Random Polynomial Time Leonard M. Adleman, Ming-Deh A. Huang |
| 1987 | Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) Johan Håstad, Frank Thomson Leighton, Mark Newman |
| 1987 | Searching a Two Key Table Under a Single Key J. Ian Munro |
| 1987 | Simple Algebras Are Difficult Lajos Rónyai |
| 1987 | Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials Erich L. Kaltofen |
| 1987 | Size-Time Complexity of Boolean Networks for Prefix Computations Gianfranco Bilardi, Franco P. Preparata |
| 1987 | Solving Minimum-Cost Flow Problems by Successive Approximation Andrew V. Goldberg, Robert Endre Tarjan |
| 1987 | Some Consequences of the Existence of Pseudorandom Generators Eric Allender |
| 1987 | Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract) Kazuo Iwano, Kenneth Steiglitz |
| 1987 | The Boolean Formula Value Problem Is in ALOGTIME Samuel R. Buss |
| 1987 | The Complexity of Cutting Convex Polytopes Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas |
| 1987 | The Complexity of Perfect Zero-Knowledge (Extended Abstract) Lance Fortnow |
| 1987 | The Decision Problem for the Probabilities of Higher-Order Properties Phokion G. Kolaitis, Moshe Y. Vardi |
| 1987 | The Pagenumber of Genus g Graphs is O(g) Lenwood S. Heath, Sorin Istrail |
| 1987 | The Power of Randomness for Communication Complexity (Preliminary Version) Martin Fürer |
| 1987 | The Strong Exponential Hierarchy Collapses Lane A. Hemachandra |
| 1987 | Threshold Spectra for Random Graphs Saharon Shelah, Joel Spencer |
| 1987 | Towards a Theory of Software Protection and Simulation by Oblivious RAMs Oded Goldreich |
| 1987 | Two Algorithms for Maintaining Order in a List Paul F. Dietz, Daniel Dominic Sleator |
| 1987 | Two Tapes Are Better than One for Off-Line Turing Machines Wolfgang Maass, Georg Schnitger, Endre Szemerédi |
| 1987 | Zero Knowledge Proofs of Identity Uriel Feige, Amos Fiat, Adi Shamir |