| 1981 | 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981 |
| 1981 | A Circuit-Size Lower Bound Ravi Kannan |
| 1981 | A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures Philippe Flajolet, Jean-Marc Steyaert |
| 1981 | A Complexity Theory Based on Boolean Algebra Sven Skyum, Leslie G. Valiant |
| 1981 | A Decidable mu-Calculus: Preliminary Report Vaughan R. Pratt |
| 1981 | A Direct Dynamic Solution to Range Search and Related Problems for Product Regions Z. Aviad, Eli Shamir |
| 1981 | A Fast Probabilistic Parallel Sorting Algorithm Rüdiger Reischuk |
| 1981 | A Minimum Spanning Ellipse Algorithm Mark J. Post |
| 1981 | A Time-Space Tradeoff for Language Recognition Pavol Duris, Zvi Galil |
| 1981 | A model of concurrent database transactions (summary) Ravi Sethi |
| 1981 | An Omega(n^4/3) Lower Bound on the Monotone Network Complexity of n-th Degree Convolution Norbert Blum |
| 1981 | Applying Parallel Computation Algorithms in the Design of Serial Algorithms Nimrod Megiddo |
| 1981 | Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version) Richard J. Lipton, Jacobo Valdes |
| 1981 | Computation of Algebraic Functions with Root Extractions Joseph F. JáJá |
| 1981 | Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract) Jeffrey Scott Vitter |
| 1981 | Global Decision Problems for Relational Databases Moshe Y. Vardi |
| 1981 | Implicit Data Structures for the Weighted Dictionary Problem (preliminary version) Greg N. Frederickson |
| 1981 | Irreducibility Testing and Factorization of Polynomials (Extended Abstract) Leonard M. Adleman, Andrew M. Odlyzko |
| 1981 | Maximum Matchings in Sparse Random Graphs Richard M. Karp, Michael Sipser |
| 1981 | New Lower Bound Techniques for VLSI Frank Thomson Leighton |
| 1981 | Non-Existence of One-Dimensional Expanding Graphs Maria M. Klawe |
| 1981 | Number Theoretic Functions Computable by Polymorphic Programs (Extended Abstract) Richard Statman |
| 1981 | On Heads Versus Tapes Wolfgang J. Paul |
| 1981 | On Relations Between Input and Communication/Computation in VLSI (Preliminary Report) Zvi M. Kedem, Alessandro Zorat |
| 1981 | On the Asymptotic Complexity of Matrix Multiplication (Extended Summary) Don Coppersmith, Shmuel Winograd |
| 1981 | On the Direct Sum Conjecture (Extended Summary) Ephraim Feig, Shmuel Winograd |
| 1981 | On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata Richard Edwin Stearns, Harry B. Hunt III |
| 1981 | On the Number of P-Isomorphism Classes of NP-Complete Sets Stephen R. Mahaney |
| 1981 | On the Relation between Descriptional Complexity and Algorithmic Probability Péter Gács |
| 1981 | On the Security of Public Key Protocols (Extended Abstract) Danny Dolev, Andrew Chi-Chih Yao |
| 1981 | Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) David S. Johnson, Anthony C. Klug |
| 1981 | Optimizing Synchronous Systems Charles E. Leiserson, James B. Saxe |
| 1981 | Parity, Circuits, and the Polynomial-Time Hierarchy Merrick L. Furst, James B. Saxe, Michael Sipser |
| 1981 | Possible Futures, Acceptances, Refusals, and Communicating Processes William C. Rounds, Stephen D. Brookes |
| 1981 | Probabilistic Algorithms in Finite Fields Michael Ben-Or |
| 1981 | Propositional Dynamic Logic of Context-Free Programs David Harel, Amir Pnueli, Jonathan Stavi |
| 1981 | Relativizing Time and Space (Preliminary Report) Ronald V. Book, Christopher B. Wilson, Mei-rui Xu |
| 1981 | Simulations among Multidimensional Turing Machines (Preliminary Version) Michael C. Loui |
| 1981 | Symmetry Breaking in Distributive Networks Alon Itai, Michael Rodeh |
| 1981 | Symmetry in Systems of Asynchronous Processes James E. Burns |
| 1981 | Temporal Logic Can Be More Expressive Pierre Wolper |
| 1981 | The Complexity of Distributed Concurrency Control Paris C. Kanellakis, Christos H. Papadimitriou |
| 1981 | The Complexity of Searching a Graph (Preliminary Version) Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
| 1981 | The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem Udi Manber, Martin Tompa |
| 1981 | The Power of Parallelism for Automatic Program Synthesis Carl H. Smith |
| 1981 | The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract) Joseph Y. Halpern, John H. Reif |
| 1981 | Time-Space Trade-Offs for General Recursion Rutger Verbeek |
| 1981 | Towards Separating Nondeterministic Time from Deterministic Time Ravi Kannan |
| 1981 | Two-Way Counter Machines and Diophantine Equations Eitan M. Gurari, Oscar H. Ibarra |
| 1981 | Unanimity in an Unknown and Unreliable Environment Danny Dolev |
| 1981 | Unbounded Program Memory Adds to the Expressive Power of First-Order Dynamic Logic (Extended Abstract) Jerzy Tiuryn |
| 1981 | Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) Christos H. Papadimitriou, Mihalis Yannakakis |