| 1986 | An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm | Zvi Galil, va Tardos |
| 1986 | On Newton's Method for Polynomials | Joel Friedman |
| 1986 | Separator-Based Strategies for Efficient Message Routing (Preliminary Version) | Greg N. Frederickson, Ravi Janardan |
| 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 | Flipping Persuasively in Constant Expected Time (Preliminary Version) | Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer |
| 1986 | Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems | Richard Cole, Uzi Vishkin |
| 1986 | Parallel Merge Sort | Richard Cole |
| 1986 | k+1 Heads Are Better than k for PDA's | Marek Chrobak, Ming Li |
| 1986 | Lower Bounds on the Complexity of Multidimensional Searching (Extended Abstract) | Bernard Chazelle |
| 1986 | On the Power of One-Way Communication | Jik H. Chang, Oscar H. Ibarra, Anastasios Vergis |
| 1986 | Information Theoretic Reductions among Disclosure Problems | Gilles Brassard, Claude Crpeau, Jean-Marc Robert |
| 1986 | Non-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond | Gilles Brassard, Claude Crpeau |
| 1986 | Optimal Simulations of Tree Machines (Preliminary Version) | Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg |
| 1986 | How Robust Is the n-Cube? (Extended Abstract) | Bernd Becker, Hans Ulrich Simon |
| 1986 | Complexity classes in communication complexity theory (preliminary version) | Lszl Babai, Peter Frankl, Janos Simon |
| 1986 | A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues | Lszl Babai |
| 1986 | Dynamic deadlock resolution protocols (Extended Abstract) | Baruch Awerbuch, Silvio Micali |
| 1986 | Meanders, Ramsey Theory and Lower Bounds for Branching Programs | Noga Alon, Wolfgang Maass |
| 1986 | Tight Complexity Bounds for Parallel Comparison Sorting | Noga Alon, Yossi Azar, Uzi Vishkin |
| 1986 | On the Power of Interaction | William Aiello, Shafi Goldwasser, Johan Hstad |
| 1986 | Storing a Dynamic Sparse Table | Alfred V. Aho, David Lee |
| 1986 | Time-Space Tradeoffs for Branching Programs Contrasted with those for Straight-Line Programs | Karl R. Abrahamson |
| 1985 | Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) | Andrew Chi-Chih Yao |
| 1985 | Design and Analysis of Dynamic Huffman Coding (Extended Abstract) | Jeffrey Scott Vitter |