| 1981 | Maximum Matchings in Sparse Random Graphs | Richard M. Karp, Michael Sipser |
| 1981 | A Circuit-Size Lower Bound | Ravi Kannan |
| 1981 | Towards Separating Nondeterministic Time from Deterministic Time | Ravi Kannan |
| 1981 | The Complexity of Distributed Concurrency Control | Paris C. Kanellakis, Christos H. Papadimitriou |
| 1981 | Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) | David S. Johnson, Anthony C. Klug |
| 1981 | Computation of Algebraic Functions with Root Extractions | Joseph F. JJ |
| 1981 | Symmetry Breaking in Distributive Networks | Alon Itai, Michael Rodeh |
| 1981 | Propositional Dynamic Logic of Context-Free Programs | David Harel, Amir Pnueli, Jonathan Stavi |
| 1981 | The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract) | Joseph Y. Halpern, John H. Reif |
| 1981 | Two-Way Counter Machines and Diophantine Equations | Eitan M. Gurari, Oscar H. Ibarra |
| 1981 | On the Relation between Descriptional Complexity and Algorithmic Probability | Pter Gcs |
| 1981 | Parity, Circuits, and the Polynomial-Time Hierarchy | Merrick L. Furst, James B. Saxe, Michael Sipser |
| 1981 | Implicit Data Structures for the Weighted Dictionary Problem (preliminary version) | Greg N. Frederickson |
| 1981 | A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures | Philippe Flajolet, Jean-Marc Steyaert |
| 1981 | On the Direct Sum Conjecture (Extended Summary) | Ephraim Feig, Shmuel Winograd |
| 1981 | A Time-Space Tradeoff for Language Recognition | Pavol Duris, Zvi Galil |
| 1981 | On the Security of Public Key Protocols (Extended Abstract) | Danny Dolev, Andrew Chi-Chih Yao |
| 1981 | Unanimity in an Unknown and Unreliable Environment | Danny Dolev |
| 1981 | On the Asymptotic Complexity of Matrix Multiplication (Extended Summary) | Don Coppersmith, Shmuel Winograd |
| 1981 | Symmetry in Systems of Asynchronous Processes | James E. Burns |
| 1981 | Relativizing Time and Space (Preliminary Report) | Ronald V. Book, Christopher B. Wilson, Mei-rui Xu |
| 1981 | An Omega(n^4/3) Lower Bound on the Monotone Network Complexity of n-th Degree Convolution | Norbert Blum |
| 1981 | Probabilistic Algorithms in Finite Fields | Michael Ben-Or |
| 1981 | A Direct Dynamic Solution to Range Search and Related Problems for Product Regions | Z. Aviad, Eli Shamir |
| 1981 | Irreducibility Testing and Factorization of Polynomials (Extended Abstract) | Leonard M. Adleman, Andrew M. Odlyzko |