| 1980 | The Equivalence Problem for Deterministic Two-Way Sequential Transducers Is Decidable | Eitan M. Gurari |
| 1980 | Polynomial-Time Algorithms for Permutation Groups | Merrick L. Furst, John E. Hopcroft, Eugene M. Luks |
| 1980 | The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries | Michael L. Fredman |
| 1980 | Implicit Data Structures with Fast Update (Preliminary Report) | Greg N. Frederickson |
| 1980 | A Distributed Abstract Data Type Implemented by a Probabilistic Communication Scheme | Nissim Francez, Michael Rodeh |
| 1980 | A Linear History Semantics for Distributed Languages (Extended Abstract) | Nissim Francez, Daniel Lehmann, Amir Pnueli |
| 1980 | The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract) | Robert W. Floyd, Jeffrey D. Ullman |
| 1980 | Exploring Binary Trees and Other Simple Trees | Philippe Flajolet, Andrew M. Odlyzko |
| 1980 | Hardware Complexity and Parallel Computation (Preliminary Version) | Patrick W. Dymond, Stephen A. Cook |
| 1980 | Efficient Uses of the Past | David P. Dobkin, J. Ian Munro |
| 1980 | Some Observations on the Average Behavior of Heapsort (Preliminary Report) | Ernst-Erich Doberkat |
| 1980 | On the Expressive Power of Attribute Grammars | Bruno Courcelle, Paul Franchi-Zannettacci |
| 1980 | Programs and Types | Robert L. Constable |
| 1980 | An Improved Algorithm for Computing With Equations | Paul Chew |
| 1980 | Structure and Complexity of Relational Queries | Ashok K. Chandra, David Harel |
| 1980 | A Recognition Algorithm for Deterministic CFLS optimal in Time and Space | Burchard von Braunmhl, Rutger Verbeek |
| 1980 | A Time-Luck Tradeoff in Cryptography | Gilles Brassard |
| 1980 | Biased 2-3 Trees | Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan |
| 1980 | A General Class of Resource Tradeoffs (Extended Abstract) | Jon Louis Bentley, Donna J. Brown |
| 1980 | On Distinguishing Prime Numbers from Composite Numbers (Abstract) | Leonard M. Adleman |
| 1979 | Some Theoretical Aspects of Position-Location Problems | Yechiam Yemini |
| 1979 | Locking Policies: Safety and Freedom from Deadlock | Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung |
| 1979 | New Classes and Applications of Hash Functions | Mark N. Wegman, Larry Carter |
| 1979 | Division Is Good | Janos Simon |
| 1979 | A T S^2 = O(2^n) Time/Space Tradeoff for Certain NP-Complete Problems | Richard Schroeppel, Adi Shamir |