| 1985 | Optimal Precision in the Presence of Uncertainty (Preliminary Version) | Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi |
| 1985 | On the Stability of the Ethernet | Jonathan Goodman, Albert G. Greenberg, Neal Madras, Peter March |
| 1985 | The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract) | Shafi Goldwasser, Silvio Micali, Charles Rackoff |
| 1985 | Compression and Ranking | Andrew V. Goldberg, Michael Sipser |
| 1985 | A Simple Three-Dimensional Real-Time Reliable Cellular Array | Pter Gcs, John H. Reif |
| 1985 | Polynomial Time Solutions of Some Problems in Computational Algebra | Katalin Friedl, Lajos Rnyai |
| 1985 | The Parallel Complexity of Exponentiating Polynomials over Finite Fields | Faith E. Fich, Martin Tompa |
| 1985 | One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation | Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson |
| 1985 | Fault Tolerance of Minimal Path Routings in a Network | Paul Feldman |
| 1985 | An Internal Semantics for Modal Logic: Preliminary Report | Ronald Fagin, Moshe Y. Vardi |
| 1985 | The Effect of Updates in Binary Search Trees | Joseph C. Culberson |
| 1985 | Equational Theories and Database Constraints | Stavros S. Cosmadakis, Paris C. Kanellakis |
| 1985 | The Distributed Firing Squad Problem (Preliminary Version) | Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer |
| 1985 | A Probabilistic Algorithm for the Post Office Problem | Kenneth L. Clarkson |
| 1985 | Self-Organizing Sequential Search and Hilbert's Inequalities | Fan R. K. Chung, D. J. Hajela, Paul D. Seymour |
| 1985 | The Complexity of Backtrack Searches (Preliminary Version) | Larry Carter, Larry J. Stockmeyer, Mark N. Wegman |
| 1985 | The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract) | Samuel R. Buss |
| 1985 | Provable Isomorphisms and Domain Equations in Models of Typed Languages (Preliminary Version) | Kim B. Bruce, Giuseppe Longo |
| 1985 | An O(\mathop lg n) Expected Rounds Randomized Byzantine Generals Protocol | Gabriel Bracha |
| 1985 | On the Expected Behaviour of Disjoint Set Union Algorithms | Bla Bollobs, Istvn Simon |
| 1985 | An Algorithm for Finding Hamilton Cycles in a Random Graph | Bla Bollobs, Trevor I. Fenner, Alan M. Frieze |
| 1985 | Finding the Median Requires 2n Comparisons | Samuel W. Bent, John W. John |
| 1985 | Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency | J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rdiger Olderog, Jeffery I. Zucker |
| 1985 | Stable Prehension with Three Fingers | Brenda S. Baker, Steven Fortune, Eric Grosse |
| 1985 | Trading Group Theory for Randomness | Lszl Babai |