| 1985 | Factoring with Cyclotomic Polynomials | Eric Bach, Jeffrey O. Shallit |
| 1985 | Distributed BFS Algorithms | Baruch Awerbuch, Robert G. Gallager |
| 1985 | Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version) | Mikhail J. Atallah, Susanne E. Hambrusch |
| 1985 | Visibility-Polygon Search and Euclidean Shortest Paths | Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai |
| 1985 | Three Theorems on Polynomial Degrees of NP-Sets | Klaus Ambos-Spies |
| 1985 | Geometrical Realization of Set Systems and Probabilistic Communication Complexity | Noga Alon, Peter Frankl, Vojtech Rdl |
| 1985 | Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) | Mikls Ajtai, Avi Wigderson |
| 1985 | Multi-Layer Grid Embeddings | Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson |
| 1985 | Parallel Computational Geometry (Extended Abstract) | Alok Aggarwal, Bernard Chazelle, Leonidas J. Guibas, Colm 'Dnlaing, Chee-Keng Yap |
| 1984 | Efficient and Secure Pseudo-Random Number Generation (Extended Abstract) | Umesh V. Vazirani, Vijay V. Vazirani |
| 1984 | A fast approximation for minimum spanning trees in k-dimensional space | Pravin M. Vaidya |
| 1984 | How to Share Memory in a Distributed System (A Preliminary Version) | Eli Upfal, Avi Wigderson |
| 1984 | Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version) | Prasoon Tiwari |
| 1984 | Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary) | Robert Endre Tarjan, Uzi Vishkin |
| 1984 | A Polynomial Time Algorithm for Fault Diagnosability | Gregory F. Sullivan |
| 1984 | An Augmenting Path Algorithm for the Parity Problem on Linear Matroids | Matthias F. M. Stallmann, Harold N. Gabow |
| 1984 | The Average-Case Analysis of Some On-Line Algorithms for Bin Packing | Peter W. Shor |
| 1984 | Shortest Paths in Euclidean Graphs (Extended Abstract) | Robert Sedgewick, Jeffrey Scott Vitter |
| 1984 | Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract) | Miklos Santha, Umesh V. Vazirani |
| 1984 | A Characterization of Probabilistic Inference | Leonard Pitt |
| 1984 | Parallel Communication with Limited Buffers (Preliminary Version) | Nicholas Pippenger |
| 1984 | Probabilistic Communication Complexity (Preliminary Version) | Ramamohan Paturi, Janos Simon |
| 1984 | A Communication-Time Tradeoff | Christos H. Papadimitriou, Jeffrey D. Ullman |
| 1984 | An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time | J. Ian Munro |
| 1984 | A Semantic Characterization of Full Abstraction for Typed Lambda Calculi | Ketan Mulmuley |