| 1979 | Transforming Static Data Structures to Dynamic Structures (Abridged Version) | James B. Saxe, Jon Louis Bentley |
| 1979 | On Uniform Circuit Complexity (Extended Abstract) | Walter L. Ruzzo |
| 1979 | Complexity of the Mover's Problem and Generalizations (Extended Abstract) | John H. Reif |
| 1979 | The Cube-Connected-Cycles: A Versatile Network for Parallel Computation (Extended Abstract) | Franco P. Preparata, Jean Vuillemin |
| 1979 | Models of Program Logics | Vaughan R. Pratt |
| 1979 | On Simultaneous Resource Bounds (Preliminary Version) | Nicholas Pippenger |
| 1979 | Computational Complexity in Algebraic Function Fields (Preliminary Version) | Nicholas Pippenger |
| 1979 | Multiple-Person Alternation | Gary L. Peterson, John H. Reif |
| 1979 | On Time versus Space II | Wolfgang J. Paul, Rdiger Reischuk |
| 1979 | Field Extension and Triangular Aggregating, Uniting and Canceling for the Acceleration of Matrix Multiplications | Victor Y. Pan |
| 1979 | Bijective A-Transducers | Hermann A. Maurer, Maurice Nivat |
| 1979 | Complexity of Partial Satisfaction | Karl J. Lieberherr, Ernst Specker |
| 1979 | Succinct Certificates for the Solvability of Binary Quadratic Diophantine Equations | J. C. Lagarias |
| 1979 | Semantics of Probabilistic Programs | Dexter Kozen |
| 1979 | Origins of Recursive Function Theory | Stephen Cole Kleene |
| 1979 | Efficient Computation of Continuous Skeletons | David G. Kirkpatrick |
| 1979 | Controlling Concurrency Using Locking Protocols (Preliminary Report) | Zvi M. Kedem, Abraham Silberschatz |
| 1979 | Length of Predicate Calculus Formulas as a New Complexity Measure | Neil Immerman |
| 1979 | Observations about the Development of Theoretical Computer Science | Juris Hartmanis |
| 1979 | Formal Languages: Origins and Directions | Sheila A. Greibach |
| 1979 | Toward Self-Organizing Linear Search (Preliminary Draught) | Gaston H. Gonnet, J. Ian Munro, Hendra Suwanda |
| 1979 | Efficient Algorithms for Simple Matroid Intersection Problems | Harold N. Gabow, Robert Endre Tarjan |
| 1979 | Explicit Constructions of Linear Size Superconcentrators | Ofer Gabber, Zvi Galil |
| 1979 | Towards Analysing Sequences of Operations for Dynamic Data Structures (Preliminary Version) | Philippe Flajolet, Jean Franon, Jean Vuillemin |
| 1979 | Resource Allocation with Immunity to Limited Process Failure (Preliminary Report) | Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin |