| 1984 | 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984 |
| 1984 | A "Paradoxical" Solution to the Signature Problem (Extended Abstract) Shafi Goldwasser, Silvio Micali, Ronald L. Rivest |
| 1984 | A Characterization of Probabilistic Inference Leonard Pitt |
| 1984 | A Communication-Time Tradeoff Christos H. Papadimitriou, Jeffrey D. Ullman |
| 1984 | A Comparative Study of X-Tree, Pyramid and Related Machines Alok Aggarwal |
| 1984 | A Lower Bound for Probabilistic Algorithms for Finite State Machines Albert G. Greenberg, Alan Weiss |
| 1984 | A Model-Theoretic Analysis of Knowledge: Preliminary Report Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi |
| 1984 | A Polynomial Solution for Potato-peeling and other Polygon Inclusion and Enclosure Problems Jyun-Sheng Chang, Chee-Keng Yap |
| 1984 | A Polynomial Time Algorithm for Fault Diagnosability Gregory F. Sullivan |
| 1984 | A Semantic Characterization of Full Abstraction for Typed Lambda Calculi Ketan Mulmuley |
| 1984 | A fast approximation for minimum spanning trees in k-dimensional space Pravin M. Vaidya |
| 1984 | An Augmenting Path Algorithm for the Parity Problem on Linear Matroids Matthias F. M. Stallmann, Harold N. Gabow |
| 1984 | An Efficient Algorithm to Find all 'Bidirectional' Edges of an Undirected Graph Bhubaneswar Mishra |
| 1984 | An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time J. Ian Munro |
| 1984 | Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version) Shlomo Moran, Marc Snir, Udi Manber |
| 1984 | Complexity Measures for Public-Key Cryptosystems (Preliminary Report) Joachim Grollmann, Alan L. Selman |
| 1984 | Computing on a Free Tree via Complexity-Preserving Mappings Bernard Chazelle |
| 1984 | Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables J. Friedman |
| 1984 | Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications Daniel Kornhauser, Gary L. Miller, Paul G. Spirakis |
| 1984 | Designing Systolic Algorithms Using Sequential Machines Oscar H. Ibarra, Michael A. Palis, Sam M. Kim |
| 1984 | Dynamic Segment Intersection Search with Applications Hiroshi Imai, Takao Asano |
| 1984 | Efficient Implementation of Graph Algorithms Using Contraction Harold N. Gabow, Zvi Galil, Thomas H. Spencer |
| 1984 | Efficient and Secure Pseudo-Random Number Generation (Extended Abstract) Umesh V. Vazirani, Vijay V. Vazirani |
| 1984 | Eigenvalues, Expanders and Superconcentrators (Extended Abstract) Noga Alon, V. D. Milman |
| 1984 | Embedding Planar Graphs in Seven Pages Lenwood S. Heath |
| 1984 | Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average (Extended Abstract) Lenore Blum, Mike Shub |
| 1984 | Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms Michael L. Fredman, Robert Endre Tarjan |
| 1984 | Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary) Robert Endre Tarjan, Uzi Vishkin |
| 1984 | Fishspear: A Priority Queue Algorithm (Extended Abstract) Michael J. Fischer, Mike Paterson |
| 1984 | Flipping coins in many pockets (Byzantine agreement on uniformly random values) Andrei Z. Broder, Danny Dolev |
| 1984 | Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract) Miklos Santha, Umesh V. Vazirani |
| 1984 | Graph Bisection Algorithms with Good Average Case Behavior Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser |
| 1984 | How to Construct Random Functions (Extended Abstract) Oded Goldreich, Shafi Goldwasser, Silvio Micali |
| 1984 | How to Share Memory in a Distributed System (A Preliminary Version) Eli Upfal, Avi Wigderson |
| 1984 | Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain Manuel Blum |
| 1984 | Interactive Data Comparison Abbas El Gamal, Alon Orlitsky |
| 1984 | Linear Congruential Generators Do Not Produce Random Sequences Alan M. Frieze, Ravi Kannan, J. C. Lagarias |
| 1984 | Linear Verification for Spanning Trees János Komlós |
| 1984 | Log Depth Circuits for Division and Related Problems Paul Beame, Stephen A. Cook, H. James Hoover |
| 1984 | Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version) Prasoon Tiwari |
| 1984 | Minimal Degrees for Honest Polynomial Reducibilities Steven Homer |
| 1984 | Mulltiplication of Polynomials over the Ring of Integers Michael Kaminski |
| 1984 | Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme Sergiu Hart, Micha Sharir |
| 1984 | On the Complexity of Matrix Group Problems I László Babai, Endre Szemerédi |
| 1984 | On the Limits to Speed Up Parallel Machines by Large Hardware and Unbounded Communication Friedhelm Meyer auf der Heide, Rüdiger Reischuk |
| 1984 | Parallel Communication with Limited Buffers (Preliminary Version) Nicholas Pippenger |
| 1984 | Parallel Powering Joachim von zur Gathen |
| 1984 | Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers Amos Fiat, Adi Shamir |
| 1984 | Probabilistic Communication Complexity (Preliminary Version) Ramamohan Paturi, Janos Simon |
| 1984 | RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr |
| 1984 | River Routing Every Which Way, but Loose (Extended Abstract) Richard Cole, Alan Siegel |
| 1984 | Semantic Models for Second-Order Lambda Calculus John C. Mitchell |
| 1984 | Shortest Paths in Euclidean Graphs (Extended Abstract) Robert Sedgewick, Jeffrey Scott Vitter |
| 1984 | Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms Richard Cole |
| 1984 | Space Searching for Intersecting Objects David P. Dobkin, Herbert Edelsbrunner |
| 1984 | Sparse Oracles and Uniform Complexity Classes José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman |
| 1984 | Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers Ravindran Kannan, Gary L. Miller, Larry Rudolph |
| 1984 | The Average-Case Analysis of Some On-Line Algorithms for Bin Packing Peter W. Shor |
| 1984 | The Multi-Tree Approach to Reliability in Distributed Networks Alon Itai, Michael Rodeh |
| 1984 | Very Fast Parallel Matrix and Polynomial Arithmetic Wayne Eberly |