| 1986 | Parallel Complexity of Logical Query Programs | Jeffrey D. Ullman, Allen Van Gelder |
| 1986 | The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication | Volker Strassen |
| 1986 | Meshes with Multiple Buses | Quentin F. Stout |
| 1986 | Geometric Applications of Davenport-Schinzel Sequences | Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony |
| 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 | An Algorithm for Constructing the Aspect Graph | W. Harry Plantinga, Charles R. Dyer |
| 1986 | The Token Distribution Problem (Preliminary Version) | David Peleg, Eli Upfal |
| 1986 | An Algorithmic Approach to the Automated Design of Parts Orienters | B. K. Natarajan |
| 1986 | What search algorithm gives optimal average-case performance when search resources are highly limited? | David Mutchler |
| 1986 | Programming Simultaneous Actions Using Common Knowledge: Preliminary Version | Yoram Moses, Mark R. Tuttle |
| 1986 | The Distance Bound for Sorting on Mesh-Connected Processor Arrays Is Tight (Preliminary Report) | Yiming Ma, Sandeep Sen, Isaac D. Scherson |
| 1986 | Parallel Algorithms for Permutation Groups and Graph Isomorphism | Eugene M. Luks |
| 1986 | A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications | Nathan Linial, Lszl Lovsz, Avi Wigderson |
| 1986 | Collapsing Degrees (Extended Abstract) | Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer |
| 1986 | An Efficient Parallel Algorithm for Planarity | Philip N. Klein, John H. Reif |
| 1986 | On a Search Problem Related to Branch-and-Bound Procedures | Richard M. Karp, Michael E. Saks, Avi Wigderson |
| 1986 | Competitive Snoopy Caching | Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel Dominic Sleator |
| 1986 | Proving by Example and Gap Theorems | Jiawei Hong |
| 1986 | Finite-Resolution Computational Geometry | Daniel H. Greene, F. Frances Yao |
| 1986 | Three Results on the Polynomial Isomorphism of Complete Sets | Judy Goldsmith, Deborah Joseph |
| 1986 | Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) | Oded Goldreich, Silvio Micali, Avi Wigderson |
| 1986 | An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph | Hillel Gazit |
| 1986 | Permanent and Determinant | Joachim von zur Gathen |
| 1986 | The Complexity of Isomorphism Testing | Max H. Garzon, Yechezkel Zalcstein |