| 1980 | The Consistency of "P = NP" and Related Problems with Fragments of Number Theory. | Richard A. DeMillo, Richard J. Lipton |
| 1980 | An Approach to The k Paths Problem | Allen Cypher |
| 1980 | Detection is Easier than Computation (Extended Abstract) | Bernard Chazelle, David P. Dobkin |
| 1980 | Graph Pebbling with Many Free Pebbles can be Difficult | David A. Carlson, John E. Savage |
| 1980 | Kraft Storage and Access for List Implementations (Extended Abstract) | Donna J. Brown |
| 1980 | The Chip Complexity of Binary Arithmetic | Richard P. Brent, H. T. Kung |
| 1980 | A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation | Allan Borodin, Stephen A. Cook |
| 1980 | A Shortest-Path Algorithm with Expected Time O(n^2 log n log ^* n) | Peter A. Bloniarz |
| 1980 | Local and Global Properties in Networks of Processors (Extended Abstract) | Dana Angluin |
| 1979 | Some Complexity Questions Related to Distributive Computing (Preliminary Report) | Andrew Chi-Chih Yao |
| 1979 | Completeness Classes in Algebra | Leslie G. Valiant |
| 1979 | Negation Can Be Exponentially Powerful | Leslie G. Valiant |
| 1979 | The recognition of Series Parallel digraphs | Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler |
| 1979 | Deadlock-Free Packet Switching Networks | Sam Toueg, Jeffrey D. Ullman |
| 1979 | Area-Time Complexity for VLSI | Clark D. Thompson |
| 1979 | Lower Bounds on the Size of Sweeping Automata | Michael Sipser |
| 1979 | On the Cryptocomplexity of Knapsack Systems | Adi Shamir |
| 1979 | The Complexity of Finding Periods | Robert Sedgewick, Thomas G. Szymanski |
| 1979 | Tree-Size Bounded Alternation | Walter L. Ruzzo |
| 1979 | Storage Representations for Tree-Like Data Structures | Arnold L. Rosenberg, Derick Wood, Zvi Galil |
| 1979 | Universal Games of Incomplete Information | John H. Reif |
| 1979 | Time-Space Trade-Offs for Asynchronous Parallel Models: Reducibilities and Equivalences | Gary L. Peterson |
| 1979 | A Programming Language Theorem Which Is Independent of Peano Arithmetic | Michael J. O'Donnell |
| 1979 | Implicit Data Structures (Preliminary Draft) | J. Ian Munro, Hendra Suwanda |
| 1979 | On the Expressive Power of Dynamic Logic (Preliminary Report) | Albert R. Meyer, Karl Winklmann |