| 1979 | A Completeness Technique for D-Axiomatizable Semantics Francine Berman |
| 1979 | A Near Optimal Data Structure for a Type of Range Query Problem Michael L. Fredman |
| 1979 | A Programming Language Theorem Which Is Independent of Peano Arithmetic Michael J. O'Donnell |
| 1979 | Area-Time Complexity for VLSI Clark D. Thompson |
| 1979 | Completeness Classes in Algebra Leslie G. Valiant |
| 1979 | Computable Queries for Relational Data Bases (Preliminary Report) Ashok K. Chandra, David Harel |
| 1979 | Computing Integrated Costs of Sequences of Operations with Application to Dictionaries Philippe Flajolet, Jean Françon, Jean Vuillemin |
| 1979 | Deadlock-Free Packet Switching Networks Sam Toueg, Jeffrey D. Ullman |
| 1979 | Decomposing a Polygon into its Convex Parts Bernard Chazelle, David P. Dobkin |
| 1979 | Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space Stephen A. Cook |
| 1979 | Equivalence of Relational Database Schemes Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman |
| 1979 | Fast Parallel Processing Array Algorithms for some Graph Problems (Preliminary Version) S. Rao Kosaraju |
| 1979 | Finding Patterns Common to a Set of Strings (Extended Abstract) Dana Angluin |
| 1979 | Implicit Data Structures (Preliminary Draft) J. Ian Munro, Hendra Suwanda |
| 1979 | Lower Bounds on the Size of Sweeping Automata Michael Sipser |
| 1979 | Minimum Covers in the Relational Database Model (Extended Abstract) David Maier |
| 1979 | Negation Can Be Exponentially Powerful Leslie G. Valiant |
| 1979 | Network Flow and Generalized Path Compression Zvi Galil, Amnon Naamad |
| 1979 | On Determining the Genus of a Graph in O(v^O(g)) Steps I. S. Filotti, Gary L. Miller, John H. Reif |
| 1979 | On a Multidimensional Search Problem (Preliminary Version) S. Rao Kosaraju |
| 1979 | On gamma-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract) Timothy J. Long |
| 1979 | On the Complexity of Bilinear Forms with Commutativity Joseph F. JáJá |
| 1979 | On the Cryptocomplexity of Knapsack Systems Adi Shamir |
| 1979 | On the Expressive Power of Dynamic Logic (Preliminary Report) Albert R. Meyer, Karl Winklmann |
| 1979 | Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, Alfred V. Aho |
| 1979 | Real-Time Simulation of Concatenable Double-Ended Queues by Double-Ended Queues (Preliminary Version) S. Rao Kosaraju |
| 1979 | Some Complexity Questions Related to Distributive Computing (Preliminary Report) Andrew Chi-Chih Yao |
| 1979 | Some Connections between Mathematical Logic and Complexity Theory Richard A. DeMillo, Richard J. Lipton |
| 1979 | Storage Representations for Tree-Like Data Structures Arnold L. Rosenberg, Derick Wood, Zvi Galil |
| 1979 | The Complexity of Finding Periods Robert Sedgewick, Thomas G. Szymanski |
| 1979 | The Complexity of Problems in Systems of Communicating Sequential Processes (Extended Abstract) Richard E. Ladner |
| 1979 | The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs Eitan M. Gurari, Oscar H. Ibarra |
| 1979 | The Pebbling Problem is Complete in Polynomial Space John R. Gilbert, Thomas Lengauer, Robert Endre Tarjan |
| 1979 | The recognition of Series Parallel digraphs Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler |
| 1979 | Time-Space Trade-Offs for Asynchronous Parallel Models: Reducibilities and Equivalences Gary L. Peterson |
| 1979 | Tree-Size Bounded Alternation Walter L. Ruzzo |
| 1979 | Universal Games of Incomplete Information John H. Reif |
| 1979 | Upper and Lower Bounds on Time-Space Tradeoffs Thomas Lengauer, Robert Endre Tarjan |