| 1978 | The Macro Model for Data Compression (Extended Abstract) | James A. Storer, Thomas G. Szymanski |
| 1978 | Computability Theory in Admissible Domains | Edward Sciore, A. Tang |
| 1978 | The Complexity of Satisfiability Problems | Thomas J. Schaefer |
| 1978 | Nondeterminism and the Size of Two Way Finite Automata | William J. Sakoda, Michael Sipser |
| 1978 | Coping with Errors in Binary Search Procedures (Preliminary Report) | Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, Joel Spencer |
| 1978 | Presburger Arithmetic with Bounded Quantifier Alternation | C. R. Reddy, Donald W. Loveland |
| 1978 | Operational and Semantic Equivalence between Recursive Programs | Jean-Claude Raoult, Jean Vuillemin |
| 1978 | Relativized Questions Involving Probabilistic Algorithms | Charles Rackoff |
| 1978 | A Practical Decision Method for Propositional Dynamic Logic: Preliminary Report | Vaughan R. Pratt |
| 1978 | Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers | Victor Y. Pan |
| 1978 | On Formulating Simultaneity for Studying Parallelism and Synchronization | Raymond E. Miller, Chee-Keng Yap |
| 1978 | On the n^log n Isomorphism Technique: A Preliminary Report | Gary L. Miller |
| 1978 | Combinatorial Optimization with Rational Objective Functions | Nimrod Megiddo |
| 1978 | Straight-Line Program Length as a Parameter for Complexity Measures | Nancy A. Lynch |
| 1978 | Maximization Problems on Graphs with Edge Weights Chosen from a Normal Distribution (Extended Abstract) | George S. Lueker |
| 1978 | On the Complexity of the Maximum Subgraph Problem | John M. Lewis |
| 1978 | The Subgraph Homeomorphism Problem | Andrea S. LaPaugh, Ronald L. Rivest |
| 1978 | Indexing of Subrecursive Classes | Dexter Kozen |
| 1978 | On the Completeness of a Generalized Matching Problem | David G. Kirkpatrick, Pavol Hell |
| 1978 | A New Solution to the Critical Section Problem | Howard P. Katseff |
| 1978 | Optimal Evaluation of Pairs of Bilinear Forms | Joseph F. JJ |
| 1978 | On the Parallel Evaluation of Multivariate Polynomials | Laurent Hyafil |
| 1978 | An NP-Complete Number-Theoretic Problem | Eitan M. Gurari, Oscar H. Ibarra |
| 1978 | A Unified Approach to Models of Synchronous Parallel Machines | Leslie M. Goldschlager |
| 1978 | Algorithms for Edge Coloring Bipartite Graphs | Harold N. Gabow, Oded Kariv |