| 1985 | Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version) | Paul M. B. Vitnyi |
| 1985 | Random Polynomial Time Is Equal to Slightly-random Polynomial Time | Umesh V. Vazirani, Vijay V. Vazirani |
| 1985 | Automatic Verification of Probabilistic Concurrent Finite-State Programs | Moshe Y. Vardi |
| 1985 | On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences | Micha Sharir, Ron Livne |
| 1985 | Inferring the Structure of a Markov Chain from its Output | Steven Rudich |
| 1985 | Motion Planning in the Presence of Moving Obstacles | John H. Reif, Micha Sharir |
| 1985 | An Optimal Parallel Algorithm for Integer Sorting | John H. Reif |
| 1985 | On Networks of Noisy Gates | Nicholas Pippenger |
| 1985 | The Complexity of Facets Resolved | Christos H. Papadimitriou, David Wolfe |
| 1985 | Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials | Victor Y. Pan |
| 1985 | An All Pairs Shortest Path Algorithm with Expected Running Time O(n^2 log n) | Alistair Moffat, Tadao Takaoka |
| 1985 | Parallel Tree Contraction and Its Application | Gary L. Miller, John H. Reif |
| 1985 | Average Case Lower Bounds on the Construction and Searching of Partial Orders | Harry G. Mairson |
| 1985 | Fast Parallel Computation with Permutation Groups | Eugene M. Luks, Pierre McKenzie |
| 1985 | Computing ears and branchings in parallel | Lszl Lovsz |
| 1985 | Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time | Ming Li |
| 1985 | Efficient String Matching in the Presence of Errors | Gad M. Landau, Uzi Vishkin |
| 1985 | Algebraic Cell Decomposition in NC (Preliminary Version) | Dexter Kozen, Chee-Keng Yap |
| 1985 | The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) | Lefteris M. Kirousis, Christos H. Papadimitriou |
| 1985 | The Complexity of Parallel Computation on Matroids | Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization | Erich L. Kaltofen |
| 1985 | How Easy Is Local Search? (Extended Abstract) | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1985 | Identification Is Easier Than Decoding | Joseph F. JJ |
| 1985 | Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks | Ming-Deh A. Huang |
| 1985 | Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results | Dorit S. Hochbaum, David B. Shmoys |