| 1984 | Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version) | Shlomo Moran, Marc Snir, Udi Manber |
| 1984 | Semantic Models for Second-Order Lambda Calculus | John C. Mitchell |
| 1984 | An Efficient Algorithm to Find all 'Bidirectional' Edges of an Undirected Graph | Bhubaneswar Mishra |
| 1984 | Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications | Daniel Kornhauser, Gary L. Miller, Paul G. Spirakis |
| 1984 | Linear Verification for Spanning Trees | Jnos Komls |
| 1984 | Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers | Ravindran Kannan, Gary L. Miller, Larry Rudolph |
| 1984 | Mulltiplication of Polynomials over the Ring of Integers | Michael Kaminski |
| 1984 | The Multi-Tree Approach to Reliability in Distributed Networks | Alon Itai, Michael Rodeh |
| 1984 | Dynamic Segment Intersection Search with Applications | Hiroshi Imai, Takao Asano |
| 1984 | Designing Systolic Algorithms Using Sequential Machines | Oscar H. Ibarra, Michael A. Palis, Sam M. Kim |
| 1984 | Minimal Degrees for Honest Polynomial Reducibilities | Steven Homer |
| 1984 | On the Limits to Speed Up Parallel Machines by Large Hardware and Unbounded Communication | Friedhelm Meyer auf der Heide, Rdiger Reischuk |
| 1984 | Embedding Planar Graphs in Seven Pages | Lenwood S. Heath |
| 1984 | Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme | Sergiu Hart, Micha Sharir |
| 1984 | Complexity Measures for Public-Key Cryptosystems (Preliminary Report) | Joachim Grollmann, Alan L. Selman |
| 1984 | A Lower Bound for Probabilistic Algorithms for Finite State Machines | Albert G. Greenberg, Alan Weiss |
| 1984 | A "Paradoxical" Solution to the Signature Problem (Extended Abstract) | Shafi Goldwasser, Silvio Micali, Ronald L. Rivest |
| 1984 | How to Construct Random Functions (Extended Abstract) | Oded Goldreich, Shafi Goldwasser, Silvio Micali |
| 1984 | Parallel Powering | Joachim von zur Gathen |
| 1984 | Interactive Data Comparison | Abbas El Gamal, Alon Orlitsky |
| 1984 | Efficient Implementation of Graph Algorithms Using Contraction | Harold N. Gabow, Zvi Galil, Thomas H. Spencer |
| 1984 | Linear Congruential Generators Do Not Produce Random Sequences | Alan M. Frieze, Ravi Kannan, J. C. Lagarias |
| 1984 | Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables | J. Friedman |
| 1984 | Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms | Michael L. Fredman, Robert Endre Tarjan |
| 1984 | Fishspear: A Priority Queue Algorithm (Extended Abstract) | Michael J. Fischer, Mike Paterson |