| 1986 | A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots Michael Ben-Or, Ephraim Feig, Dexter Kozen, Prasoon Tiwari |
| 1986 | A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field Ketan Mulmuley |
| 1986 | A Linear-Time Algorithm for Triangulating Simple Polygons Robert Endre Tarjan, Christopher J. Van Wyk |
| 1986 | A New Approach to the Maximum Flow Problem Andrew V. Goldberg, Robert Endre Tarjan |
| 1986 | A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract) Ker-I Ko, Timothy J. Long, Ding-Zhu Du |
| 1986 | A Provably Efficient Algorithm for Dynamic Storage Allocation Edward G. Coffman Jr., Frank Thomson Leighton |
| 1986 | Almost All Primes Can Be Quickly Certified Shafi Goldwasser, Joe Kilian |
| 1986 | Almost Optimal Lower Bounds for Small Depth Circuits Johan Håstad |
| 1986 | An Optimal Sorting Algorithm for Mesh Connected Computers Claus-Peter Schnorr, Adi Shamir |
| 1986 | Aspects of Information Flow in VLSI Circuits (Extended Abstract) Alan Siegel |
| 1986 | Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ David A. Mix Barrington |
| 1986 | Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract) Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth |
| 1986 | Computing the Volume Is Difficult Imre Bárány, Zoltán Füredi |
| 1986 | Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face Raimund Seidel |
| 1986 | Deterministic Selection in O(log log N) Parallel Time Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi |
| 1986 | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms Richard Cole, Uzi Vishkin |
| 1986 | Explicit Expanders and the Ramanujan Conjectures Alexander Lubotzky, Ralph Phillips, Peter Sarnak |
| 1986 | Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows Sanjiv Kapoor, Pravin M. Vaidya |
| 1986 | Fault Tolerance in Networks of Bounded Degree (Preliminary Version) Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal |
| 1986 | Finding Irreducible Polynomials over Finite Fields Leonard M. Adleman, Hendrik W. Lenstra Jr. |
| 1986 | Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract) Mihalis Yannakakis |
| 1986 | Further Applications of Random Sampling to Computational Geometry Kenneth L. Clarkson |
| 1986 | How hard is to marry at random? (On the approximation of the permanent) Andrei Z. Broder |
| 1986 | Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm Gad M. Landau, Uzi Vishkin |
| 1986 | Limits on the Power of Concurrent-Write Parallel Machines Paul Beame |
| 1986 | Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract) Richard Cleve |
| 1986 | Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version) George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran |
| 1986 | Making Data Structures Persistent James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan |
| 1986 | New Lower Bounds for Parallel Computation Ming Li, Yaacov Yesha |
| 1986 | Non-Blocking Networks (Preliminary Version) Paul Feldman, Joel Friedman, Nicholas Pippenger |
| 1986 | On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines Zvi Galil, Ravi Kannan, Endre Szemerédi |
| 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 | Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version) Anna R. Karlin, Eli Upfal |
| 1986 | Private Coins versus Public Coins in Interactive Proof Systems Shafi Goldwasser, Michael Sipser |
| 1986 | Probing Convex Polytopes David P. Dobkin, Herbert Edelsbrunner, Chee-Keng Yap |
| 1986 | Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA Juris Hartmanis |
| 1986 | Pseudo-random Permutation Generators and Cryptographic Composition Michael Luby, Charles Rackoff |
| 1986 | Reasoning about Fair Concurrent Programs Costas Courcoubetis, Moshe Y. Vardi, Pierre Wolper |
| 1986 | Rotation Distance, Triangulations, and Hyperbolic Geometry Daniel Dominic Sleator, Robert Endre Tarjan, William P. Thurston |
| 1986 | The Complexity of Optimization Problems Mark W. Krentel |
| 1986 | The Complexity of Reasoning about Knowledge and Time: Extended Abstract Joseph Y. Halpern, Moshe Y. Vardi |
| 1986 | Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms Frank Thomson Leighton, Peter W. Shor |
| 1986 | Topologically Sweeping an Arrangement Herbert Edelsbrunner, Leonidas J. Guibas |
| 1986 | Two Probabilistic Results on Rectilinear Steiner Trees Marshall W. Bern |
| 1986 | Two lower bounds for branching programs Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, György Turán |
| 1986 | Uniform Closure Properties of P-Computable Functions Erich L. Kaltofen |
| 1986 | With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy Jin-Yi Cai |