| 1980 | A Complete Axiomatization for a Large Class of Dependencies in Relational Databases Fereidoon Sadri, Jeffrey D. Ullman |
| 1980 | A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata Esko Ukkonen |
| 1980 | A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper) I. S. Filotti, Jack N. Mayer |
| 1980 | A Shortest-Path Algorithm with Expected Time O(n^2 log n log ^* n) Peter A. Bloniarz |
| 1980 | A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation Allan Borodin, Stephen A. Cook |
| 1980 | An Approach to The k Paths Problem Allen Cypher |
| 1980 | An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version) Wolfgang J. Paul, Joel I. Seiferas, Janos Simon |
| 1980 | An Optimal Solution to a Wire-Routing Problem (Preliminary Version) Martin Tompa |
| 1980 | Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version) Nicholas Pippenger |
| 1980 | Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations Grazyna Mirkowska |
| 1980 | Complexity of Implementations on the Level of Algebraic Specifications Hartmut Ehrig, Bernd Mahr |
| 1980 | Critical Path Scheduling of Task Systems with Resource and Processor Constraints (Extended Abstract) Errol L. Lloyd |
| 1980 | Deadlock- and Livelock-Free Packet Switching Networks Sam Toueg |
| 1980 | Definability in Dynamic Logic Albert R. Meyer, Rohit Parikh |
| 1980 | Detection is Easier than Computation (Extended Abstract) Bernard Chazelle, David P. Dobkin |
| 1980 | Dynamic Algebras and the Nature of Induction Vaughan R. Pratt |
| 1980 | Dynamically Maintaining Configurations in the Plane (Detailed Abstract) Mark H. Overmars, Jan van Leeuwen |
| 1980 | Efficient Dynamic Programming Using Quadrangle Inequalities F. Frances Yao |
| 1980 | Fast Allocation of Nearby Resources in a Distributed System Nancy A. Lynch |
| 1980 | Generalized Selection and Ranking (Preliminary Version) Greg N. Frederickson, Donald B. Johnson |
| 1980 | Graph Pebbling with Many Free Pebbles can be Difficult David A. Carlson, John E. Savage |
| 1980 | Heuristics for Weighted Perfect Matching Kenneth J. Supowit, David A. Plaisted, Edward M. Reingold |
| 1980 | Horn Clauses and Database Dependencies (Extended Abstract) Ronald Fagin |
| 1980 | Independence Results in Computer Science? (Preliminary Version) Deborah Joseph, Paul Young |
| 1980 | Isomorphism Testing for Graphs of Bounded Genus Gary L. Miller |
| 1980 | Isomorphism for Graphs Embeddable on the Projective Plane David Lichtenstein |
| 1980 | Kraft Storage and Access for List Implementations (Extended Abstract) Donna J. Brown |
| 1980 | Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract) Richard M. Karp, Robert Endre Tarjan |
| 1980 | Local and Global Properties in Networks of Processors (Extended Abstract) Dana Angluin |
| 1980 | Logics for Probabilistic Programming (Extended Abstract) John H. Reif |
| 1980 | On Some Deterministic Space Complexity Problems Jia-Wei Hong |
| 1980 | On Translating a Set of Rectangles Leonidas J. Guibas, F. Frances Yao |
| 1980 | On the Distribution of Independent Formulae of Number Theory David A. Plaisted |
| 1980 | Optimal Tree Layout (Preliminary Version) Michael J. Fischer, Mike Paterson |
| 1980 | Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, Richard J. Lipton |
| 1980 | Random Matroids John H. Reif, Paul G. Spirakis |
| 1980 | Some Connections between Nonuniform and Uniform Complexity Classes Richard M. Karp, Richard J. Lipton |
| 1980 | Space-time Tradeoffs and First Order Problems in a Model of Programs Chee-Keng Yap |
| 1980 | Testing Isomorphism on Cone Graphs (Extended Abstract) Christoph M. Hoffmann |
| 1980 | Testing Polynomials which Are Easy to Compute (Extended Abstract) Joos Heintz, Claus-Peter Schnorr |
| 1980 | The Chip Complexity of Binary Arithmetic Richard P. Brent, H. T. Kung |
| 1980 | The Complexity of the Equivalence Problem for Straight-Line Programs Oscar H. Ibarra, Brian S. Leininger |
| 1980 | The Consistency of "P = NP" and Related Problems with Fragments of Number Theory. Richard A. DeMillo, Richard J. Lipton |
| 1980 | The Node Cost Measure for Embedding Graphs on the Planar Grid (Extended Abstract) James A. Storer |
| 1980 | The Orbit Problem is Decidable Ravindran Kannan, Richard J. Lipton |
| 1980 | Time-Space Tradeoffs for some Algebraic Problems Joseph F. JáJá |
| 1980 | Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations Martin Tompa |
| 1980 | Vector Execution of Flow Graphs (Extended Abstract) H. Raymond Strong |