| 1981 | A Data Structure for Dynamic Trees | Daniel Dominic Sleator, Robert Endre Tarjan |
| 1981 | Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version) | Janos Simon |
| 1981 | Distributed Algorithms for Synchronizing Interprocess Communication within Real Time | John H. Reif, Paul G. Spirakis |
| 1981 | Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) | Mike Paterson, Walter L. Ruzzo, Lawrence Snyder |
| 1981 | On the Faithful Regular Extensions of Iterative Algebras | Francesco Parisi-Presicce |
| 1981 | The Complexity of Dynamic Languages and Dynamic Optimization Problems | James B. Orlin |
| 1981 | Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems | David E. Muller, Paul E. Schupp |
| 1981 | Bandwidth Constrained NP-Complete Problems | Burkhard Monien, Ivan Hal Sudborough |
| 1981 | An Algorithm for the General Petri Net Reachability Problem | Ernst W. Mayr |
| 1981 | Lower Bounds for VLSI | Richard J. Lipton, Robert Sedgewick |
| 1981 | The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories) | Daniel Leivant |
| 1981 | Examples of Hard Tautologies in the Propositional Calculus | Balakrishnan Krishnamurthy, Robert N. Moll |
| 1981 | Localized Search in Sorted Lists | S. Rao Kosaraju |
| 1981 | New Layouts for the Shuffle-Exchange Graph (Extended Abstract) | Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller |
| 1981 | Measures of Parallelism in Alternating Computation Trees (Extended Abstract) | K. N. King |
| 1981 | Digital Straightness and Convexity (Extended Abstract) | Chul E. Kim, Azriel Rosenfeld |
| 1981 | Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract) | Deborah Joseph, Paul Young |
| 1981 | Graphs that Are Almost Binary Trees (Preliminary Version) | Jia-Wei Hong, Arnold L. Rosenberg |
| 1981 | I/O Complexity: The Red-Blue Pebble Game | Jia-Wei Hong, H. T. Kung |
| 1981 | Classes of Functions for Computing on Binary Trees (Extended Abstract) | Frank M. Hawrusik, K. N. Venkataraman, Ann Yasuhara |
| 1981 | A Linear Probing Sort and its Analysis (Preliminary Draft) | Gaston H. Gonnet, J. Ian Munro |
| 1981 | Time-Space-Optimal String Matching | Zvi Galil, Joel I. Seiferas |
| 1981 | An Efficient General Purpose Parallel Computer | Zvi Galil, Wolfgang J. Paul |
| 1981 | Lower Bounds for the Cycle Detection Problem | Faith E. Fich |
| 1981 | Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version) | Pavol Duris, Zvi Galil |