| 1981 | Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract) | Jeffrey Scott Vitter |
| 1981 | Time-Space Trade-Offs for General Recursion | Rutger Verbeek |
| 1981 | Global Decision Problems for Relational Databases | Moshe Y. Vardi |
| 1981 | Unbounded Program Memory Adds to the Expressive Power of First-Order Dynamic Logic (Extended Abstract) | Jerzy Tiuryn |
| 1981 | On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata | Richard Edwin Stearns, Harry B. Hunt III |
| 1981 | Number Theoretic Functions Computable by Polymorphic Programs (Extended Abstract) | Richard Statman |
| 1981 | The Power of Parallelism for Automatic Program Synthesis | Carl H. Smith |
| 1981 | A Complexity Theory Based on Boolean Algebra | Sven Skyum, Leslie G. Valiant |
| 1981 | A model of concurrent database transactions (summary) | Ravi Sethi |
| 1981 | Possible Futures, Acceptances, Refusals, and Communicating Processes | William C. Rounds, Stephen D. Brookes |
| 1981 | A Fast Probabilistic Parallel Sorting Algorithm | Rdiger Reischuk |
| 1981 | A Decidable mu-Calculus: Preliminary Report | Vaughan R. Pratt |
| 1981 | A Minimum Spanning Ellipse Algorithm | Mark J. Post |
| 1981 | On Heads Versus Tapes | Wolfgang J. Paul |
| 1981 | Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1981 | The Complexity of Searching a Graph (Preliminary Version) | Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
| 1981 | Applying Parallel Computation Algorithms in the Design of Serial Algorithms | Nimrod Megiddo |
| 1981 | The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem | Udi Manber, Martin Tompa |
| 1981 | On the Number of P-Isomorphism Classes of NP-Complete Sets | Stephen R. Mahaney |
| 1981 | Simulations among Multidimensional Turing Machines (Preliminary Version) | Michael C. Loui |
| 1981 | Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version) | Richard J. Lipton, Jacobo Valdes |
| 1981 | Optimizing Synchronous Systems | Charles E. Leiserson, James B. Saxe |
| 1981 | New Lower Bound Techniques for VLSI | Frank Thomson Leighton |
| 1981 | Non-Existence of One-Dimensional Expanding Graphs | Maria M. Klawe |
| 1981 | On Relations Between Input and Communication/Computation in VLSI (Preliminary Report) | Zvi M. Kedem, Alessandro Zorat |