| 1978 | Selection and Sorting with Limited Storage | J. Ian Munro, Mike Paterson |
| 1978 | A Data Structure for Orthogonal Range Queries | George S. Lueker |
| 1978 | Model Theoretic Aspects of Computational Complexity | Richard J. Lipton |
| 1978 | GO Is PSPACE Hard | David Lichtenstein, Michael Sipser |
| 1978 | Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus | Harry R. Lewis |
| 1978 | On the Algebra of Order (Extended Abstract) | Daniel J. Lehmann |
| 1978 | Alternating Pushdown Automata (Preliminary Report) | Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer |
| 1978 | Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract) | Akira Kanda |
| 1978 | One-Way Log-Tape Reductions | Juris Hartmanis, Neil Immerman, Stephen R. Mahaney |
| 1978 | A Dichromatic Framework for Balanced Trees | Leonidas J. Guibas, Robert Sedgewick |
| 1978 | A New Algorithm for the Maximal Flow Problem | Zvi Galil |
| 1978 | Description and Analysis of an Efficient Priority Queue Representation | Jean Franon, Grard Viennot, Jean Vuillemin |
| 1978 | The Complexity of Checkers on an N * N Board - Preliminary Report | Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha |
| 1978 | Consistent and Complete Proof Rules for the Total Correctness of Parallel Programs | Lawrence Flon, Norihisa Suzuki |
| 1978 | Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages | Joost Engelfriet, Grzegorz Rozenberg |
| 1978 | On Recursive Equations Having a Unique Solution | Bruno Courcelle |
| 1978 | Improving the Bounds on Optimal Merging | C. Christen |
| 1978 | Computable Nondeterministic Functions | Ashok K. Chandra |
| 1978 | On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs) | Manuel Blum, Dexter Kozen |
| 1978 | Two Theorems on Random Polynomial Time | Leonard M. Adleman |
| 1978 | Lower Bounds on Information Transfer in Distributed Computations | Harold Abelson |
| 1977 | Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) | Andrew Chi-Chih Yao |
| 1977 | The Typed lambda-Calculus Is not Elementary Recursive | Richard Statman |
| 1977 | On Uniquely Represented Data Structures (Extended Abstract) | Lawrence Snyder |
| 1977 | The Category-Theoretic Solution of Recursive Domain Equations (Extended Abstract) | Michael B. Smyth, Gordon D. Plotkin |