| 1986 | Finding Irreducible Polynomials over Finite Fields | Leonard M. Adleman, Hendrik W. Lenstra Jr. |
| 1985 | A General Approach to d-Dimensional Geometric Queries (Extended Abstract) | Andrew Chi-Chih Yao, F. Frances Yao |
| 1985 | White Pebbles Help | Robert E. Wilber |
| 1985 | The Two-Processor Scheduling Problem is in R-NC | Umesh V. Vazirani, Vijay V. Vazirani |
| 1985 | Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract) | Umesh V. Vazirani |
| 1985 | Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report | Moshe Y. Vardi, Larry J. Stockmeyer |
| 1985 | NP Is as Easy as Detecting Unique Solutions | Leslie G. Valiant, Vijay V. Vazirani |
| 1985 | Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract) | Pravin M. Vaidya |
| 1985 | Multicommodity Flows in Planar Undirected Graphs and Shortest Paths | Hitoshi Suzuki, Takao Nishizeki, Nobuji Saito |
| 1985 | Provably Good Routing in Graphs: Regular Arrays | Prabhakar Raghavan, Clark D. Thompson |
| 1985 | Concurrent Dynamic Logic (Extended Abstract) | David Peleg |
| 1985 | Efficient Parallel Solution of Linear Systems | Victor Y. Pan, John H. Reif |
| 1985 | A Simple Parallel Algorithm for the Maximal Independent Set Problem | Michael Luby |
| 1985 | Doubly Lexical Orderings of Matrices | Anna Lubiw |
| 1985 | One-Way Functions and Pseudorandom Generators | Leonid A. Levin |
| 1985 | Algorithms for Routing and Testing Routability of Planar VLSI Layouts | Charles E. Leiserson, F. Miller Maley |
| 1985 | Are Search and Decision Problems Computationally Equivalent? | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | Constructing a Perfect Matching is in Random NC | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors | Erich L. Kaltofen |
| 1985 | Expanders Obtained from Affine Transformations (Preliminary Version) | Shuji Jimbo, Akira Maruoka |
| 1985 | The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems | Dung T. Huynh |
| 1985 | Riemann Hypothesis and Finding Roots over Finite Fields | Ming-Deh A. Huang |
| 1985 | Fast Algorithms for N-Dimensional Restrictions of Hard Problems | Friedhelm Meyer auf der Heide |
| 1985 | The Cryptographic Security of Truncated Linearly Related Variables | Johan Hstad, Adi Shamir |
| 1985 | A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems | Dov Harel |