| 1982 | Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract) | Dan E. Willard |
| 1982 | A New Approximate Graph Coloring Algorithm | Avi Wigderson |
| 1982 | Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines | Paul M. B. Vitnyi |
| 1982 | The Complexity of Relational Query Languages (Extended Abstract) | Moshe Y. Vardi |
| 1982 | The Complexity of Propositional Linear Temporal Logics | A. Prasad Sistla, Edmund M. Clarke |
| 1982 | Space-Bounded Hierarchies and Probabilistic Computations | Walter L. Ruzzo, Janos Simon, Martin Tompa |
| 1982 | How to Reuse a "Write-Once" Memory (Preliminary Version). | Ronald L. Rivest, Adi Shamir |
| 1982 | Symmetric Complementation | John H. Reif |
| 1982 | Probabilistic Simulations (Preliminary Version) | Nicholas Pippenger |
| 1982 | The Complexity of Facets (and Some Facets of Complexity) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1982 | Communication Complexity | Christos H. Papadimitriou, Michael Sipser |
| 1982 | A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms | Jan K. Pachl, Ephraim Korach, Doron Rotem |
| 1982 | Ensembles Reconnaissables de Mots Biinfinis | Maurice Nivat, Dominique Perrin |
| 1982 | Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract) | Kurt Mehlhorn, Erik Meineche Schmidt |
| 1982 | Probabilistic, Nondeterministic, and Alternating Decision Trees | Udi Manber, Martin Tompa |
| 1982 | A Layout Strategy for VLSI which Is Provably Good (Extended Abstract) | Frank Thomson Leighton |
| 1982 | On the Random Oracle Hypothesis | Stuart A. Kurtz |
| 1982 | Decidability of Reachability in Vector Addition Systems (Preliminary Version) | S. Rao Kosaraju |
| 1982 | Measuring Energy Consumption in VLSI Circuits: a Foundation | Gloria Kissin |
| 1982 | A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization | Erich L. Kaltofen |
| 1982 | Two-Dimensional Alternating Turing Machines | Katsushi Inoue, Itsuo Takanami, Hiroshi Taniguchi |
| 1982 | Relational Queries Computable in Polynomial Time (Extended Abstract) | Neil Immerman |
| 1982 | Notes on Merging Networks (Preliminary Version) | Zhu Hong, Robert Sedgewick |
| 1982 | Trees, Automata, and Games | Yuri Gurevich, Leo Harrington |
| 1982 | On the Time Complexity of Broadcast Communication Schemes (Preliminary Version) | Albert G. Greenberg |