| 1984 | Digital Disks and a Digital Compactness Measure | Chul E. Kim, Timothy A. Anderson |
| 1984 | A Fast Parallel Algorithm for the Maximal Independent Set Problem | Richard M. Karp, Avi Wigderson |
| 1984 | A Probabilistic Analysis of Multidimensional Bin Packing Problems | Richard M. Karp, Michael Luby, Alberto Marchetti-Spaccamela |
| 1984 | A New Polynomial-Time Algorithm for Linear Programming | Narendra Karmarkar |
| 1984 | Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers | Ravindran Kannan, Arjen K. Lenstra, Lszl Lovsz |
| 1984 | Every Poset Has a Good Comparison | Jeff Kahn, Michael E. Saks |
| 1984 | Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields | Ming-Deh A. Huang |
| 1984 | Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems | Dorit S. Hochbaum, David B. Shmoys |
| 1984 | Modelling Fair Processes | Matthew Hennessy |
| 1984 | Probabilistic Temporal Logics for Finite and Bounded Models | Sergiu Hart, Micha Sharir |
| 1984 | A General Result on Infinite Trees and Its Applications (Preliminary Report) | David Harel |
| 1984 | Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract) | Gaston H. Gonnet |
| 1984 | On Finding the Exact Solution of a Zero-One Knapsack Problem | Andrew V. Goldberg, Alberto Marchetti-Spaccamela |
| 1984 | Transition Logic: How to Reason About Temporal Properties in a Compositional Way | Rob Gerth |
| 1984 | Optimal Parallel Algorithms for String Matching | Zvi Galil |
| 1984 | Scaling and Related Techniques for Geometry Problems | Harold N. Gabow, Jon Louis Bentley, Robert Endre Tarjan |
| 1984 | Data Structures for On-Line Updating of Matroid Intersection Solutions (Preliminary Version) | Greg N. Frederickson, Mandayam A. Srinivas |
| 1984 | The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring | Greg N. Frederickson, Nancy A. Lynch |
| 1984 | An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals | Deborah S. Franzblau, Daniel J. Kleitman |
| 1984 | Deciding Branching Time Logic | E. Allen Emerson, A. Prasad Sistla |
| 1984 | Lower Bounds on Communication Complexity | Pavol Duris, Zvi Galil, Georg Schnitger |
| 1984 | Correcting Faults in Write-Once Memory | Danny Dolev, David Maier, Harry G. Mairson, Jeffrey D. Ullman |
| 1984 | A New Look at Fault Tolerant Network Routing | Danny Dolev, Joseph Y. Halpern, Barbara Simons, H. Raymond Strong |
| 1984 | On the Possibility and Impossibility of Achieving Clock Synchronization | Danny Dolev, Joseph Y. Halpern, H. Raymond Strong |
| 1984 | Liveness Properties as Convergence in Metric Spaces | Pierpaolo Degano, Ugo Montanari |