| 1980 | On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report) | F. Frances Yao |
| 1980 | Algebraic Dependencies (Extended Abstract) | Mihalis Yannakakis, Christos H. Papadimitriou |
| 1980 | On a Class of Totally Unimodular Matrices | Mihalis Yannakakis |
| 1980 | Parsing for Structural Editors (Extended Abstract) | Mark N. Wegman |
| 1980 | A Combinatorial Limit to the Computing Power of V.L.S.I. Circuits (Extended Abstract) | Jean Vuillemin |
| 1980 | Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract) | Jeffrey Scott Vitter |
| 1980 | Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes | Ivan Hal Sudborough |
| 1980 | A Fast Algorithm for Multiprocessor Scheduling | Barbara Simons |
| 1980 | N-Process Synchronization by 4 log _2 N-Valued Shared Variables | Michael O. Rabin |
| 1980 | Succinct Representation, Random Strings, and Complexity Classes | Gary L. Peterson |
| 1980 | An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs | Silvio Micali, Vijay V. Vazirani |
| 1980 | Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis | Stephen R. Mahaney |
| 1980 | Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time | Eugene M. Luks |
| 1980 | Area-Efficient Graph Layouts (for VLSI) | Charles E. Leiserson |
| 1980 | A Polynomial Time Algorithm for Optimal Routing around a Rectangle (Extended Abstract) | Andrea S. LaPaugh |
| 1980 | Loop Elimination and Loop Reduction-A Model-Theoretic Analysis of Programs (Partial Report) | A. J. Kfoury |
| 1980 | On Linear Characterizations of Combinatorial Optimization Problems | Richard M. Karp, Christos H. Papadimitriou |
| 1980 | Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra | Neil D. Jones, Steven S. Muchnick |
| 1980 | Upper and Lower Bounds for First Order Expressibility | Neil Immerman |
| 1980 | Some Theorems about Matrix Multiplication (Extended Abstract) | T. C. Hu, M. T. Shing |
| 1980 | The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract) | Harry B. Hunt III, Daniel J. Rosenkrantz |
| 1980 | Proofs by Induction in Equational Theories with Constructors | Grard P. Huet, Jean-Marie Hullot |
| 1980 | On Similarity and Duality of Computation (Extended Abstract) | Jia-Wei Hong |
| 1980 | Process Logic: Expressiveness, Decidability, Completeness | David Harel, Dexter Kozen, Rohit Parikh |
| 1980 | A Linear Time Algorithm for the Lowest Common Ancestors Problem (Extended Abstract) | Dov Harel |