| 1986 | 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986 |
| 1986 | A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues László Babai |
| 1986 | A New Pebble Game that Characterizes Parallel Complexity Classes H. Venkateswaran, Martin Tompa |
| 1986 | A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications Nathan Linial, László Lovász, Avi Wigderson |
| 1986 | An Algorithm for Constructing the Aspect Graph W. Harry Plantinga, Charles R. Dyer |
| 1986 | An Algorithmic Approach to the Automated Design of Parts Orienters B. K. Natarajan |
| 1986 | An Efficient Parallel Algorithm for Planarity Philip N. Klein, John H. Reif |
| 1986 | An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm Zvi Galil, Éva Tardos |
| 1986 | An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph Hillel Gazit |
| 1986 | An optimal algorithm for the All-Nearest-Neighbors Problem Pravin M. Vaidya |
| 1986 | Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems Richard Cole, Uzi Vishkin |
| 1986 | Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract) Paul M. B. Vitányi, Baruch Awerbuch |
| 1986 | Collapsing Degrees (Extended Abstract) Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer |
| 1986 | Competitive Snoopy Caching Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel Dominic Sleator |
| 1986 | Complexity classes in communication complexity theory (preliminary version) László Babai, Peter Frankl, Janos Simon |
| 1986 | Dynamic deadlock resolution protocols (Extended Abstract) Baruch Awerbuch, Silvio Micali |
| 1986 | FFD Bin Packing for Item Sizes with Distributions on [0,1/2] Sally Floyd, Richard M. Karp |
| 1986 | Fast Solution of Some Random NP-Hard Problems Martin E. Dyer, Alan M. Frieze |
| 1986 | Finite-Resolution Computational Geometry Daniel H. Greene, F. Frances Yao |
| 1986 | Flipping Persuasively in Constant Expected Time (Preliminary Version) Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer |
| 1986 | Geometric Applications of Davenport-Schinzel Sequences Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony |
| 1986 | How Robust Is the n-Cube? (Extended Abstract) Bernd Becker, Hans Ulrich Simon |
| 1986 | How to Generate and Exchange Secrets (Extended Abstract) Andrew Chi-Chih Yao |
| 1986 | Information Theoretic Reductions among Disclosure Problems Gilles Brassard, Claude Crépeau, Jean-Marc Robert |
| 1986 | Lower Bounds for Accessing Binary Search Trees With Rotations (Preliminary Version) Robert E. Wilber |
| 1986 | Lower Bounds on the Complexity of Multidimensional Searching (Extended Abstract) Bernard Chazelle |
| 1986 | Meanders, Ramsey Theory and Lower Bounds for Branching Programs Noga Alon, Wolfgang Maass |
| 1986 | Meshes with Multiple Buses Quentin F. Stout |
| 1986 | Non-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond Gilles Brassard, Claude Crépeau |
| 1986 | On Newton's Method for Polynomials Joel Friedman |
| 1986 | On a Search Problem Related to Branch-and-Bound Procedures Richard M. Karp, Michael E. Saks, Avi Wigderson |
| 1986 | On the Power of Interaction William Aiello, Shafi Goldwasser, Johan Håstad |
| 1986 | On the Power of One-Way Communication Jik H. Chang, Oscar H. Ibarra, Anastasios Vergis |
| 1986 | Optimal Simulations of Tree Machines (Preliminary Version) Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg |
| 1986 | Parallel Algorithms for Permutation Groups and Graph Isomorphism Eugene M. Luks |
| 1986 | Parallel Complexity of Logical Query Programs Jeffrey D. Ullman, Allen Van Gelder |
| 1986 | Parallel Merge Sort Richard Cole |
| 1986 | Permanent and Determinant Joachim von zur Gathen |
| 1986 | Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments Ady Wiernik |
| 1986 | Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees Michael E. Saks, Avi Wigderson |
| 1986 | Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs Prabhakar Raghavan |
| 1986 | Programming Simultaneous Actions Using Common Knowledge: Preliminary Version Yoram Moses, Mark R. Tuttle |
| 1986 | Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | Proving by Example and Gap Theorems Jiawei Hong |
| 1986 | Separator-Based Strategies for Efficient Message Routing (Preliminary Version) Greg N. Frederickson, Ravi Janardan |
| 1986 | Storing a Dynamic Sparse Table Alfred V. Aho, David Lee |
| 1986 | The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication Volker Strassen |
| 1986 | The Complexity of Isomorphism Testing Max H. Garzon, Yechezkel Zalcstein |
| 1986 | The Distance Bound for Sorting on Mesh-Connected Processor Arrays Is Tight (Preliminary Report) Yiming Ma, Sandeep Sen, Isaac D. Scherson |
| 1986 | The Token Distribution Problem (Preliminary Version) David Peleg, Eli Upfal |
| 1986 | Three Results on the Polynomial Isomorphism of Complete Sets Judy Goldsmith, Deborah Joseph |
| 1986 | Tight Complexity Bounds for Parallel Comparison Sorting Noga Alon, Yossi Azar, Uzi Vishkin |
| 1986 | Time-Space Tradeoffs for Branching Programs Contrasted with those for Straight-Line Programs Karl R. Abrahamson |
| 1986 | What search algorithm gives optimal average-case performance when search resources are highly limited? David Mutchler |
| 1986 | k+1 Heads Are Better than k for PDA's Marek Chrobak, Ming Li |