| 1979 | On a General Method for Maximizing and Minimizing among Certain Geometric Problems (Extended Abstract) | David P. Dobkin, Lawrence Snyder |
| 1979 | Orderings for Term-Rewriting Systems | Nachum Dershowitz |
| 1979 | Approximate Algorithms for Optimization of Busy Waiting in Parallel Programs (Preliminary Report) | Edmund M. Clarke, Lishing Liu |
| 1979 | Relativized Cryptography | Gilles Brassard |
| 1979 | A Time-Space Tradeoff for Sorting on Non-Oblivious Machines | Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa |
| 1979 | The Decidability of the Equivalence of Context-Free Grammar Forms | Meera Blattner |
| 1979 | Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages | Theodore P. Baker, Juris Hartmanis |
| 1979 | Canonical Labelling of Graphs in Linear Average Time | Lszl Babai, Ludek Kucera |
| 1979 | A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables per Inequality | Bengt Aspvall, Yossi Shiloach |
| 1979 | Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems | Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Lszl Lovsz, Charles Rackoff |
| 1979 | Modeling Communications Protocols by Automata | Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1979 | Reductions that Lie | Leonard M. Adleman, Kenneth L. Manders |
| 1979 | A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography (Abstract) | Leonard M. Adleman |
| 1978 | On Lifted Problems (Preliminary Reports) | Chee-Keng Yap |
| 1978 | On the Average-case Complexity of Selecting k-th Best | Andrew Chi-Chih Yao, F. Frances Yao |
| 1978 | Should Tables Be Sorted? (Extended Abstract) | Andrew Chi-Chih Yao |
| 1978 | An Optimal Lower Bound on the Number of Total Operations to Compute 0-1 Polynomials over the Field of Complex Numbers | Jean-Paul Van de Wiele |
| 1978 | Halting Space-Bounded Computations | Michael Sipser |
| 1978 | A Fast Algorithm for Single Processor Scheduling | Barbara Simons |
| 1978 | On Tape-Bounded Probabilistic Turing Machine Transducers (Extended Abstract) | Janos Simon, John Gill, James Hunt |
| 1978 | Limited Subsets of a Free Monoid | Imre Simon |
| 1978 | Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version) | Rdiger Reischuk |
| 1978 | On Alternation (Preliminary Version) | Wolfgang J. Paul, Ernst-Jrgen Prau, Rdiger Reischuk |
| 1978 | A Decidability Result for a Second Order Process Logic | Rohit Parikh |
| 1978 | Strassen's Algorithm Is not Optimal: Trililnear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations | Victor Y. Pan |