| 1985 | A Parallel Algorithm for the Maximal Path Problem | Richard Anderson |
| 1985 | Expanders, Sorting in Rounds and Superconcentrators of Limited Depth | Noga Alon |
| 1985 | Dual Integer Linear Programs and the Relationship between their Optima | Ron Aharoni, Paul Erds, Nathan Linial |
| 1985 | Tradeoffs for VLSI Models with Subpolynomial Delay | Alok Aggarwal |
| 1984 | Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report) | Dan E. Willard |
| 1984 | Distributed Elections in an Archimedean Ring of Processors (Preliminary Version) | Paul M. B. Vitnyi |
| 1984 | Randomized Speed-Ups in Parallel Computation | Uzi Vishkin |
| 1984 | Automata Theoretic Techniques for Modal Logics of Programs (Extended Abstract) | Moshe Y. Vardi, Pierre Wolper |
| 1984 | A Theory of the Learnable | Leslie G. Valiant |
| 1984 | A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version) | Eli Upfal |
| 1984 | On Tape Versus Core; An Application of Space Efficient Perfect Hash Functions to the Invariance of Space | Cees F. Slot, Peter van Emde Boas |
| 1984 | Amortized Efficiency of List Update Rules | Daniel Dominic Sleator, Robert Endre Tarjan |
| 1984 | On Shortest Paths in Polyhedral Spaces | Micha Sharir, Amir Schorr |
| 1984 | Uniform Definability on Finite Structures with Successor | Michel de Rougemont |
| 1984 | Minimum Spanning Ellipsoids | Mark J. Post |
| 1984 | Communication with Secrecy Constraints | Alon Orlitsky, Abbas El Gamal |
| 1984 | An Efficient Signature Scheme Based on Quadratic Equations | H. Ong, Claus-Peter Schnorr, Adi Shamir |
| 1984 | Channel Routing in VLSI (Extended Abstract) | Andranik Mirzaian |
| 1984 | Finding Small Simple Cycle Separators for 2-Connected Planar Graphs | Gary L. Miller |
| 1984 | On Maintaining Dynamic Information in a Concurrent Environment (Preliminary Version) | Udi Manber |
| 1984 | Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract) | Wolfgang Maass |
| 1984 | Problems, Complete in "Average" Instance | Leonid A. Levin |
| 1984 | Tight Bounds on the Complexity of Parallel Sorting | Frank Thomson Leighton |
| 1984 | Pebblings, Edgings, and Equational Logic | Dexter Kozen |
| 1984 | On Monotone Formulae with Restricted Depth (Preliminary Version) | Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis |