| 1984 | Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers | Amos Fiat, Adi Shamir |
| 1984 | A Model-Theoretic Analysis of Knowledge: Preliminary Report | Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi |
| 1984 | Very Fast Parallel Matrix and Polynomial Arithmetic | Wayne Eberly |
| 1984 | Space Searching for Intersecting Objects | David P. Dobkin, Herbert Edelsbrunner |
| 1984 | River Routing Every Which Way, but Loose (Extended Abstract) | Richard Cole, Alan Siegel |
| 1984 | Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms | Richard Cole |
| 1984 | Computing on a Free Tree via Complexity-Preserving Mappings | Bernard Chazelle |
| 1984 | A Polynomial Solution for Potato-peeling and other Polygon Inclusion and Enclosure Problems | Jyun-Sheng Chang, Chee-Keng Yap |
| 1984 | Graph Bisection Algorithms with Good Average Case Behavior | Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser |
| 1984 | Flipping coins in many pockets (Byzantine agreement on uniformly random values) | Andrei Z. Broder, Danny Dolev |
| 1984 | Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average (Extended Abstract) | Lenore Blum, Mike Shub |
| 1984 | Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain | Manuel Blum |
| 1984 | Log Depth Circuits for Division and Related Problems | Paul Beame, Stephen A. Cook, H. James Hoover |
| 1984 | Sparse Oracles and Uniform Complexity Classes | Jos L. Balczar, Ronald V. Book, Timothy J. Long, Uwe Schning, Alan L. Selman |
| 1984 | On the Complexity of Matrix Group Problems I | Lszl Babai, Endre Szemerdi |
| 1984 | Eigenvalues, Expanders and Superconcentrators (Extended Abstract) | Noga Alon, V. D. Milman |
| 1984 | RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure | Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr |
| 1984 | A Comparative Study of X-Tree, Pyramid and Related Machines | Alok Aggarwal |
| 1983 | Lower Bounds by Probabilistic Arguments (Extended Abstract) | Andrew Chi-Chih Yao |
| 1983 | A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract) | Mihalis Yannakakis |
| 1983 | Reasoning about Infinite Computation Paths (Extended Abstract) | Pierre Wolper, Moshe Y. Vardi, A. Prasad Sistla |
| 1983 | Relativized Circuit Complexity | Christopher B. Wilson |
| 1983 | Randomness and the Density of Hard Problems | Robert E. Wilber |
| 1983 | Optimum Algorithms for Two Random Sampling Problems (Extended Abstract) | Jeffrey Scott Vitter |
| 1983 | Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) | Uzi Vishkin, Avi Wigderson |