| 1984 | Average Case Selection | Walter Cunto, J. Ian Munro |
| 1984 | Evaluating Logarithms in GF(2^n) | Don Coppersmith |
| 1984 | On k-hulls and Related Problems | Richard Cole, Micha Sharir, Chee-Keng Yap |
| 1984 | Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees (Extended Abstract) | Kenneth L. Clarkson |
| 1984 | Intersecting Is Easier than Sorting | Bernard Chazelle |
| 1984 | On the Pagenumber of Planar Graphs | Jonathan F. Buss, Peter W. Shor |
| 1984 | Efficient Fault Tolerant Routings in Networks | Andrei Z. Broder, Danny Dolev, Michael J. Fischer, Barbara Simons |
| 1984 | Threshold Functions and Bounded Depth Monotone Circuits | Ravi B. Boppana |
| 1984 | Building a Complete Inverted File for a Set of Text Files in Linear Time | Anselm Blumer, J. Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell |
| 1984 | An Area-Maximum Edge Length Tradeoff for VLSI Layout | Norbert Blum |
| 1984 | A Minimum Area VLSI Network for O(log n) Time Sorting | Gianfranco Bilardi, Franco P. Preparata |
| 1984 | Some Unexpected Expected Behavior Results for Bin Packing | Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch |
| 1984 | The Complexity of Elementary Algebra and Geometry (Preliminary Abstract) | Michael Ben-Or, Dexter Kozen, John H. Reif |
| 1984 | Now You May Compose Temporal Logic Specifications | Howard Barringer, Ruurd Kuiper, Amir Pnueli |
| 1984 | Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract) | Eric Bach, Gary L. Miller, Jeffrey O. Shallit |
| 1984 | Finding Euler Circuits in Logarithmic Parallel Time | Baruch Awerbuch, Amos Israeli, Yossi Shiloach |
| 1984 | An Efficient Network Synchronization Protocol | Baruch Awerbuch |
| 1984 | Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (Extended Abstract) | Helmut Alt |
| 1984 | A Theorem on Probabilistic Constant Depth Computations | Mikls Ajtai, Michael Ben-Or |
| 1984 | A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension | Ilan Adler, Nimrod Megiddo |
| 1983 | Some Structural Properties of Polynomial Reducibilities and Sets in NP | Paul Young |
| 1983 | A 3-Space Partition and Its Applications (Extended Abstract) | F. Frances Yao |
| 1983 | Exponential Lower Bounds for Restricted Monotone Circuits | Leslie G. Valiant |
| 1983 | Probabilistic Analysis of Bandwidth Minimization Algorithms | Jonathan S. Turner |
| 1983 | Topological Matching | Quentin F. Stout |