| 1981 | A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini |
| 1981 | A Data Structure for Dynamic Trees Daniel Dominic Sleator, Robert Endre Tarjan |
| 1981 | A Difference in Efficiency between Synchronous and Asynchronous Systems Eshrat Arjomandi, Michael J. Fischer, Nancy A. Lynch |
| 1981 | A Linear Probing Sort and its Analysis (Preliminary Draft) Gaston H. Gonnet, J. Ian Munro |
| 1981 | A Model of Computation for VLSI with Related Complexity Results Bernard Chazelle, Louis Monier |
| 1981 | An Algorithm for the General Petri Net Reachability Problem Ernst W. Mayr |
| 1981 | An Efficient General Purpose Parallel Computer Zvi Galil, Wolfgang J. Paul |
| 1981 | Bandwidth Constrained NP-Complete Problems Burkhard Monien, Ivan Hal Sudborough |
| 1981 | Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) Mike Paterson, Walter L. Ruzzo, Lawrence Snyder |
| 1981 | Classes of Functions for Computing on Binary Trees (Extended Abstract) Frank M. Hawrusik, K. N. Venkataraman, Ann Yasuhara |
| 1981 | Convex Decompositions of Polyhedra Bernard Chazelle |
| 1981 | Digital Straightness and Convexity (Extended Abstract) Chul E. Kim, Azriel Rosenfeld |
| 1981 | Distributed Algorithms for Synchronizing Interprocess Communication within Real Time John H. Reif, Paul G. Spirakis |
| 1981 | Embedded Implicational Dependencies and their Inference Problem Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky |
| 1981 | Equations between Regular Terms and an Application to Process Logic Ashok K. Chandra, Joseph Y. Halpern, Albert R. Meyer, Rohit Parikh |
| 1981 | Examples of Hard Tautologies in the Propositional Calculus Balakrishnan Krishnamurthy, Robert N. Moll |
| 1981 | Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract) Deborah Joseph, Paul Young |
| 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 |
| 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 | Issues of Correctness in Database Concurrency Control by Locking Mihalis Yannakakis |
| 1981 | LALR(k) Testing is PSPACE-Complete Esko Ukkonen, Eljas Soisalon-Soininen |
| 1981 | Localized Search in Sorted Lists S. Rao Kosaraju |
| 1981 | Low Level Complexity for Combinatorial Games Akeo Adachi, Shigeki Iwata, Takumi Kasai |
| 1981 | Lower Bounds for VLSI Richard J. Lipton, Robert Sedgewick |
| 1981 | Lower Bounds for the Cycle Detection Problem Faith E. Fich |
| 1981 | Measures of Parallelism in Alternating Computation Trees (Extended Abstract) K. N. King |
| 1981 | New Layouts for the Shuffle-Exchange Graph (Extended Abstract) Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller |
| 1981 | On the Faithful Regular Extensions of Iterative Algebras Francesco Parisi-Presicce |
| 1981 | On the Parallel Computation for the Knapsack Problem Andrew Chi-Chih Yao |
| 1981 | Optimal Wiring between Rectangles Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, Jeffrey D. Ullman |
| 1981 | Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA Ronald L. Rivest, Georgia I. Davida, Walter A. Burkhard, Richard J. Lipton |
| 1981 | Properties of Acyclic Database Schemes Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1981 | Propositional Dynamic Logic of Looping and Converse Robert S. Streett |
| 1981 | Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems David E. Muller, Paul E. Schupp |
| 1981 | Reversal Complexity of Counter Machines Tat-hung Chan |
| 1981 | Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version) Janos Simon |
| 1981 | The Complexity of Dynamic Languages and Dynamic Optimization Problems James B. Orlin |
| 1981 | The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories) Daniel Leivant |
| 1981 | The Entropic Limitations on VLSI Computations (Extended Abstract) Andrew Chi-Chih Yao |
| 1981 | The omega-Sequence Equivalence Problem for DOL Systems Is Decidable Karel Culík II, Tero Harju |
| 1981 | Time-Space-Optimal String Matching Zvi Galil, Joel I. Seiferas |
| 1981 | Unique Normal Forms in Term Rewriting Systems with Repeated Variables Paul Chew |
| 1981 | Universal Schemes for Parallel Communication Leslie G. Valiant, Gordon J. Brebner |