| 1985 | The Least Weight Subsequence Problem (Extended Abstract) | Daniel S. Hirschberg, Lawrence L. Larmore |
| 1985 | The Complexity of Parallel Sorting | Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1985 | Nondeterministic versus Probabilistic Linear Search Algorithms | Friedhelm Meyer auf der Heide |
| 1985 | Fixed-Point Extensions of First-Order Logic | Yuri Gurevich, Saharon Shelah |
| 1985 | Randomized Routing on Fat-Trees (Preliminary Version) | Ronald I. Greenberg, Charles E. Leiserson |
| 1985 | Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC | Zvi Galil, Victor Y. Pan |
| 1985 | A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract) | Zvi Galil, Stuart Haber, Moti Yung |
| 1985 | A Scaling Algorithm for Weighted Matching on General Graphs | Harold N. Gabow |
| 1985 | Recognizing Circle Graphs in Polynomial Time | Csaba P. Gabor, Wen-Lian Hsu, Kenneth J. Supowit |
| 1985 | An Application of Simultaneous Approximation in Combinatorial Optimization | Andrs Frank, va Tardos |
| 1985 | Dynamic Monotone Priorities on Planar Sets (Extended Abstract) | Michael J. Fischer, Mike Paterson |
| 1985 | Byzantine Agreement in Constant Expected Time (and Trusting No One) | Paul Feldman, Silvio Micali |
| 1985 | Equivalences and Transformations of Recursive Definitions | Bruno Courcelle |
| 1985 | On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract) | Richard Cole, Alan Siegel |
| 1985 | A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract) | Josh D. Cohen, Michael J. Fischer |
| 1985 | Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract) | Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch |
| 1985 | The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) | Benny Chor, Oded Goldreich, Johan Hstad, Joel Friedman, Steven Rudich, Roman Smolensky |
| 1985 | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract) | Benny Chor, Oded Goldreich |
| 1985 | An Almost Linear Time and O(n log n + e) Messages Distributed Algorithm for Minimum-Weight Spanning Trees | Francis Y. L. Chin, H. F. Ting |
| 1985 | Slimming Down Search Structures: A Functional Approach to Algorithm Design | Bernard Chazelle |
| 1985 | Robin Hood Hashing (Preliminary Report) | Pedro Celis, Per-ke Larson, J. Ian Munro |
| 1985 | Amplification of Probabilistic Boolean Formulas | Ravi B. Boppana |
| 1985 | Partial Polymorphic Type Inference Is Undecidable | Hans-Juergen Boehm |
| 1985 | Why Certain Subgraph Computations Require Only Linear Time | Marshall W. Bern, Eugene L. Lawler, A. L. Wong |
| 1985 | Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values | Michael Ben-Or, Nathan Linial |