| 1980 | On the Distribution of Independent Formulae of Number Theory | David A. Plaisted |
| 1980 | Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version) | Nicholas Pippenger |
| 1980 | An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version) | Wolfgang J. Paul, Joel I. Seiferas, Janos Simon |
| 1980 | Dynamically Maintaining Configurations in the Plane (Detailed Abstract) | Mark H. Overmars, Jan van Leeuwen |
| 1980 | Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations | Grazyna Mirkowska |
| 1980 | Isomorphism Testing for Graphs of Bounded Genus | Gary L. Miller |
| 1980 | Definability in Dynamic Logic | Albert R. Meyer, Rohit Parikh |
| 1980 | Fast Allocation of Nearby Resources in a Distributed System | Nancy A. Lynch |
| 1980 | Critical Path Scheduling of Task Systems with Resource and Processor Constraints (Extended Abstract) | Errol L. Lloyd |
| 1980 | Isomorphism for Graphs Embeddable on the Projective Plane | David Lichtenstein |
| 1980 | Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract) | Richard M. Karp, Robert Endre Tarjan |
| 1980 | Some Connections between Nonuniform and Uniform Complexity Classes | Richard M. Karp, Richard J. Lipton |
| 1980 | The Orbit Problem is Decidable | Ravindran Kannan, Richard J. Lipton |
| 1980 | Independence Results in Computer Science? (Preliminary Version) | Deborah Joseph, Paul Young |
| 1980 | Time-Space Tradeoffs for some Algebraic Problems | Joseph F. JJ |
| 1980 | The Complexity of the Equivalence Problem for Straight-Line Programs | Oscar H. Ibarra, Brian S. Leininger |
| 1980 | On Some Deterministic Space Complexity Problems | Jia-Wei Hong |
| 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 | On Translating a Set of Rectangles | Leonidas J. Guibas, F. Frances Yao |
| 1980 | Generalized Selection and Ranking (Preliminary Version) | Greg N. Frederickson, Donald B. Johnson |
| 1980 | Optimal Tree Layout (Preliminary Version) | Michael J. Fischer, Mike Paterson |
| 1980 | A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper) | I. S. Filotti, Jack N. Mayer |
| 1980 | Horn Clauses and Database Dependencies (Extended Abstract) | Ronald Fagin |
| 1980 | Complexity of Implementations on the Level of Algebraic Specifications | Hartmut Ehrig, Bernd Mahr |