| 1986 | The Complexity of Reasoning about Knowledge and Time: Extended Abstract | Joseph Y. Halpern, Moshe Y. Vardi |
| 1986 | Private Coins versus Public Coins in Interactive Proof Systems | Shafi Goldwasser, Michael Sipser |
| 1986 | Almost All Primes Can Be Quickly Certified | Shafi Goldwasser, Joe Kilian |
| 1986 | A New Approach to the Maximum Flow Problem | Andrew V. Goldberg, Robert Endre Tarjan |
| 1986 | On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines | Zvi Galil, Ravi Kannan, Endre Szemerdi |
| 1986 | Non-Blocking Networks (Preliminary Version) | Paul Feldman, Joel Friedman, Nicholas Pippenger |
| 1986 | Topologically Sweeping an Arrangement | Herbert Edelsbrunner, Leonidas J. Guibas |
| 1986 | Fault Tolerance in Networks of Bounded Degree (Preliminary Version) | Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal |
| 1986 | Making Data Structures Persistent | James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan |
| 1986 | Probing Convex Polytopes | David P. Dobkin, Herbert Edelsbrunner, Chee-Keng Yap |
| 1986 | Reasoning about Fair Concurrent Programs | Costas Courcoubetis, Moshe Y. Vardi, Pierre Wolper |
| 1986 | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms | Richard Cole, Uzi Vishkin |
| 1986 | A Provably Efficient Algorithm for Dynamic Storage Allocation | Edward G. Coffman Jr., Frank Thomson Leighton |
| 1986 | Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract) | Richard Cleve |
| 1986 | Further Applications of Random Sampling to Computational Geometry | Kenneth L. Clarkson |
| 1986 | With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy | Jin-yi Cai |
| 1986 | How hard is to marry at random? (On the approximation of the permanent) | Andrei Z. Broder |
| 1986 | Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract) | Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth |
| 1986 | Two Probabilistic Results on Rectilinear Steiner Trees | Marshall W. Bern |
| 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 | Limits on the Power of Concurrent-Write Parallel Machines | Paul Beame |
| 1986 | Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ | David A. Mix Barrington |
| 1986 | Computing the Volume Is Difficult | Imre Brny, Zoltn Fredi |
| 1986 | Deterministic Selection in O(log log N) Parallel Time | Mikls Ajtai, Jnos Komls, William L. Steiger, Endre Szemerdi |
| 1986 | Two lower bounds for branching programs | Mikls Ajtai, Lszl Babai, Pter Hajnal, Jnos Komls, Pavel Pudlk, Vojtech Rdl, Endre Szemerdi, Gyrgy Turn |