| 1984 | A Fast Parallel Algorithm for the Maximal Independent Set Problem Richard M. Karp, Avi Wigderson |
| 1984 | A General Result on Infinite Trees and Its Applications (Preliminary Report) David Harel |
| 1984 | A Minimum Area VLSI Network for O(log n) Time Sorting Gianfranco Bilardi, Franco P. Preparata |
| 1984 | A New Look at Fault Tolerant Network Routing Danny Dolev, Joseph Y. Halpern, Barbara Simons, H. Raymond Strong |
| 1984 | A New Polynomial-Time Algorithm for Linear Programming Narendra Karmarkar |
| 1984 | A Probabilistic Analysis of Multidimensional Bin Packing Problems Richard M. Karp, Michael Luby, Alberto Marchetti-Spaccamela |
| 1984 | A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version) Eli Upfal |
| 1984 | A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension Ilan Adler, Nimrod Megiddo |
| 1984 | A Theorem on Probabilistic Constant Depth Computations Miklós Ajtai, Michael Ben-Or |
| 1984 | A Theory of the Learnable Leslie G. Valiant |
| 1984 | Amortized Efficiency of List Update Rules Daniel Dominic Sleator, Robert Endre Tarjan |
| 1984 | An Algorithm for Constructing Regions with Rectangles: Independence and Minimum Generating Sets for Collections of Intervals Deborah S. Franzblau, Daniel J. Kleitman |
| 1984 | An Area-Maximum Edge Length Tradeoff for VLSI Layout Norbert Blum |
| 1984 | An Efficient Network Synchronization Protocol Baruch Awerbuch |
| 1984 | An Efficient Signature Scheme Based on Quadratic Equations H. Ong, Claus-Peter Schnorr, Adi Shamir |
| 1984 | Automata Theoretic Techniques for Modal Logics of Programs (Extended Abstract) Moshe Y. Vardi, Pierre Wolper |
| 1984 | Average Case Selection Walter Cunto, J. Ian Munro |
| 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 | Channel Routing in VLSI (Extended Abstract) Andranik Mirzaian |
| 1984 | Communication with Secrecy Constraints Alon Orlitsky, Abbas El Gamal |
| 1984 | Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (Extended Abstract) Helmut Alt |
| 1984 | Correcting Faults in Write-Once Memory Danny Dolev, David Maier, Harry G. Mairson, Jeffrey D. Ullman |
| 1984 | Data Structures for On-Line Updating of Matroid Intersection Solutions (Preliminary Version) Greg N. Frederickson, Mandayam A. Srinivas |
| 1984 | Deciding Branching Time Logic E. Allen Emerson, A. Prasad Sistla |
| 1984 | Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract) Gaston H. Gonnet |
| 1984 | Digital Disks and a Digital Compactness Measure Chul E. Kim, Timothy A. Anderson |
| 1984 | Distributed Elections in an Archimedean Ring of Processors (Preliminary Version) Paul M. B. Vitányi |
| 1984 | Efficient Fault Tolerant Routings in Networks Andrei Z. Broder, Danny Dolev, Michael J. Fischer, Barbara Simons |
| 1984 | Evaluating Logarithms in GF(2^n) Don Coppersmith |
| 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 | Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees (Extended Abstract) Kenneth L. Clarkson |
| 1984 | Finding Euler Circuits in Logarithmic Parallel Time Baruch Awerbuch, Amos Israeli, Yossi Shiloach |
| 1984 | Finding Small Simple Cycle Separators for 2-Connected Planar Graphs Gary L. Miller |
| 1984 | Intersecting Is Easier than Sorting Bernard Chazelle |
| 1984 | Liveness Properties as Convergence in Metric Spaces Pierpaolo Degano, Ugo Montanari |
| 1984 | Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report) Dan E. Willard |
| 1984 | Lower Bounds on Communication Complexity Pavol Duris, Zvi Galil, Georg Schnitger |
| 1984 | Minimum Spanning Ellipsoids Mark J. Post |
| 1984 | Modelling Fair Processes Matthew Hennessy |
| 1984 | Now You May Compose Temporal Logic Specifications Howard Barringer, Ruurd Kuiper, Amir Pnueli |
| 1984 | On Finding the Exact Solution of a Zero-One Knapsack Problem Andrew V. Goldberg, Alberto Marchetti-Spaccamela |
| 1984 | On Maintaining Dynamic Information in a Concurrent Environment (Preliminary Version) Udi Manber |
| 1984 | On Monotone Formulae with Restricted Depth (Preliminary Version) Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis |
| 1984 | On Shortest Paths in Polyhedral Spaces Micha Sharir, Amir Schorr |
| 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 | On k-hulls and Related Problems Richard Cole, Micha Sharir, Chee-Keng Yap |
| 1984 | On the Pagenumber of Planar Graphs Jonathan F. Buss, Peter W. Shor |
| 1984 | On the Possibility and Impossibility of Achieving Clock Synchronization Danny Dolev, Joseph Y. Halpern, H. Raymond Strong |
| 1984 | Optimal Parallel Algorithms for String Matching Zvi Galil |
| 1984 | Pebblings, Edgings, and Equational Logic Dexter Kozen |
| 1984 | Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers Ravindran Kannan, Arjen K. Lenstra, László Lovász |
| 1984 | Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems Dorit S. Hochbaum, David B. Shmoys |
| 1984 | Probabilistic Temporal Logics for Finite and Bounded Models Sergiu Hart, Micha Sharir |
| 1984 | Problems, Complete in "Average" Instance Leonid A. Levin |
| 1984 | Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA Richard A. DeMillo |
| 1984 | Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract) Wolfgang Maass |
| 1984 | Randomized Speed-Ups in Parallel Computation Uzi Vishkin |
| 1984 | Scaling and Related Techniques for Geometry Problems Harold N. Gabow, Jon Louis Bentley, Robert Endre Tarjan |
| 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 | Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract) Eric Bach, Gary L. Miller, Jeffrey O. Shallit |
| 1984 | The Complexity of Elementary Algebra and Geometry (Preliminary Abstract) Michael Ben-Or, Dexter Kozen, John H. Reif |
| 1984 | The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring Greg N. Frederickson, Nancy A. Lynch |
| 1984 | Threshold Functions and Bounded Depth Monotone Circuits Ravi B. Boppana |
| 1984 | Tight Bounds on the Complexity of Parallel Sorting Frank Thomson Leighton |
| 1984 | Transition Logic: How to Reason About Temporal Properties in a Compositional Way Rob Gerth |
| 1984 | Uniform Definability on Finite Structures with Successor Michel de Rougemont |