| 1979 | Minimum Covers in the Relational Database Model (Extended Abstract) | David Maier |
| 1979 | On gamma-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract) | Timothy J. Long |
| 1979 | Upper and Lower Bounds on Time-Space Tradeoffs | Thomas Lengauer, Robert Endre Tarjan |
| 1979 | The Complexity of Problems in Systems of Communicating Sequential Processes (Extended Abstract) | Richard E. Ladner |
| 1979 | Real-Time Simulation of Concatenable Double-Ended Queues by Double-Ended Queues (Preliminary Version) | S. Rao Kosaraju |
| 1979 | Fast Parallel Processing Array Algorithms for some Graph Problems (Preliminary Version) | S. Rao Kosaraju |
| 1979 | On a Multidimensional Search Problem (Preliminary Version) | S. Rao Kosaraju |
| 1979 | On the Complexity of Bilinear Forms with Commutativity | Joseph F. JJ |
| 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 | Network Flow and Generalized Path Compression | Zvi Galil, Amnon Naamad |
| 1979 | A Near Optimal Data Structure for a Type of Range Query Problem | Michael L. Fredman |
| 1979 | Computing Integrated Costs of Sequences of Operations with Application to Dictionaries | Philippe Flajolet, Jean Franon, Jean Vuillemin |
| 1979 | On Determining the Genus of a Graph in O(v^O(g)) Steps | I. S. Filotti, Gary L. Miller, John H. Reif |
| 1979 | Some Connections between Mathematical Logic and Complexity Theory | Richard A. DeMillo, Richard J. Lipton |
| 1979 | Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space | Stephen A. Cook |
| 1979 | Decomposing a Polygon into its Convex Parts | Bernard Chazelle, David P. Dobkin |
| 1979 | Computable Queries for Relational Data Bases (Preliminary Report) | Ashok K. Chandra, David Harel |
| 1979 | A Completeness Technique for D-Axiomatizable Semantics | Francine Berman |
| 1979 | Equivalence of Relational Database Schemes | Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman |
| 1979 | Finding Patterns Common to a Set of Strings (Extended Abstract) | Dana Angluin |
| 1978 | Node- and Edge-Deletion NP-Complete Problems | Mihalis Yannakakis |
| 1978 | Switching Functions Whose Monotone Complexity Is Nearly Quadratic | Ingo Wegener |
| 1978 | Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of their Circuits | Martin Tompa |
| 1978 | Data Type Specification: Parameterization and the Power of Specification Techniques | James W. Thatcher, Eric G. Wagner, Jesse B. Wright |