| 1980 | 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980 |
| 1980 | A Combinatorial Limit to the Computing Power of V.L.S.I. Circuits (Extended Abstract) Jean Vuillemin |
| 1980 | A Distributed Abstract Data Type Implemented by a Probabilistic Communication Scheme Nissim Francez, Michael Rodeh |
| 1980 | A Fast Algorithm for Multiprocessor Scheduling Barbara Simons |
| 1980 | A General Class of Resource Tradeoffs (Extended Abstract) Jon Louis Bentley, Donna J. Brown |
| 1980 | A Linear History Semantics for Distributed Languages (Extended Abstract) Nissim Francez, Daniel Lehmann, Amir Pnueli |
| 1980 | A Linear Time Algorithm for the Lowest Common Ancestors Problem (Extended Abstract) Dov Harel |
| 1980 | A Polynomial Time Algorithm for Optimal Routing around a Rectangle (Extended Abstract) Andrea S. LaPaugh |
| 1980 | A Recognition Algorithm for Deterministic CFLS optimal in Time and Space Burchard von Braunmühl, Rutger Verbeek |
| 1980 | A Time-Luck Tradeoff in Cryptography Gilles Brassard |
| 1980 | Algebraic Dependencies (Extended Abstract) Mihalis Yannakakis, Christos H. Papadimitriou |
| 1980 | An Improved Algorithm for Computing With Equations Paul Chew |
| 1980 | An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs Silvio Micali, Vijay V. Vazirani |
| 1980 | Area-Efficient Graph Layouts (for VLSI) Charles E. Leiserson |
| 1980 | Biased 2-3 Trees Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan |
| 1980 | Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra Neil D. Jones, Steven S. Muchnick |
| 1980 | Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes Ivan Hal Sudborough |
| 1980 | Efficient Uses of the Past David P. Dobkin, J. Ian Munro |
| 1980 | Exploring Binary Trees and Other Simple Trees Philippe Flajolet, Andrew M. Odlyzko |
| 1980 | Hardware Complexity and Parallel Computation (Preliminary Version) Patrick W. Dymond, Stephen A. Cook |
| 1980 | Implicit Data Structures with Fast Update (Preliminary Report) Greg N. Frederickson |
| 1980 | Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time Eugene M. Luks |
| 1980 | Loop Elimination and Loop Reduction-A Model-Theoretic Analysis of Programs (Partial Report) A. J. Kfoury |
| 1980 | N-Process Synchronization by 4 log _2 N-Valued Shared Variables Michael O. Rabin |
| 1980 | On Distinguishing Prime Numbers from Composite Numbers (Abstract) Leonard M. Adleman |
| 1980 | On Linear Characterizations of Combinatorial Optimization Problems Richard M. Karp, Christos H. Papadimitriou |
| 1980 | On Similarity and Duality of Computation (Extended Abstract) Jia-Wei Hong |
| 1980 | On a Class of Totally Unimodular Matrices Mihalis Yannakakis |
| 1980 | On the Expressive Power of Attribute Grammars Bruno Courcelle, Paul Franchi-Zannettacci |
| 1980 | On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report) F. Frances Yao |
| 1980 | Parsing for Structural Editors (Extended Abstract) Mark N. Wegman |
| 1980 | Polynomial-Time Algorithms for Permutation Groups Merrick L. Furst, John E. Hopcroft, Eugene M. Luks |
| 1980 | Process Logic: Expressiveness, Decidability, Completeness David Harel, Dexter Kozen, Rohit Parikh |
| 1980 | Programs and Types Robert L. Constable |
| 1980 | Proofs by Induction in Equational Theories with Constructors Gérard P. Huet, Jean-Marie Hullot |
| 1980 | Some Observations on the Average Behavior of Heapsort (Preliminary Report) Ernst-Erich Doberkat |
| 1980 | Some Theorems about Matrix Multiplication (Extended Abstract) T. C. Hu, M. T. Shing |
| 1980 | Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis Stephen R. Mahaney |
| 1980 | Structure and Complexity of Relational Queries Ashok K. Chandra, David Harel |
| 1980 | Succinct Representation, Random Strings, and Complexity Classes Gary L. Peterson |
| 1980 | The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract) Robert W. Floyd, Jeffrey D. Ullman |
| 1980 | The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract) Harry B. Hunt III, Daniel J. Rosenkrantz |
| 1980 | The Equivalence Problem for Deterministic Two-Way Sequential Transducers Is Decidable Eitan M. Gurari |
| 1980 | The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries Michael L. Fredman |
| 1980 | Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract) Jeffrey Scott Vitter |
| 1980 | Upper and Lower Bounds for First Order Expressibility Neil Immerman |