| 1981 | Optimal Wiring between Rectangles | Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, Jeffrey D. Ullman |
| 1981 | The omega-Sequence Equivalence Problem for DOL Systems Is Decidable | Karel Culk II, Tero Harju |
| 1981 | Unique Normal Forms in Term Rewriting Systems with Repeated Variables | Paul Chew |
| 1981 | A Model of Computation for VLSI with Related Complexity Results | Bernard Chazelle, Louis Monier |
| 1981 | Convex Decompositions of Polyhedra | Bernard Chazelle |
| 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 | Reversal Complexity of Counter Machines | Tat-hung Chan |
| 1981 | A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines | Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini |
| 1981 | Properties of Acyclic Database Schemes | Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1981 | A Difference in Efficiency between Synchronous and Asynchronous Systems | Eshrat Arjomandi, Michael J. Fischer, Nancy A. Lynch |
| 1981 | Low Level Complexity for Combinatorial Games | Akeo Adachi, Shigeki Iwata, Takumi Kasai |
| 1980 | Space-time Tradeoffs and First Order Problems in a Model of Programs | Chee-Keng Yap |
| 1980 | Efficient Dynamic Programming Using Quadrangle Inequalities | F. Frances Yao |
| 1980 | A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata | Esko Ukkonen |
| 1980 | Deadlock- and Livelock-Free Packet Switching Networks | Sam Toueg |
| 1980 | Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations | Martin Tompa |
| 1980 | An Optimal Solution to a Wire-Routing Problem (Preliminary Version) | Martin Tompa |
| 1980 | Heuristics for Weighted Perfect Matching | Kenneth J. Supowit, David A. Plaisted, Edward M. Reingold |
| 1980 | Vector Execution of Flow Graphs (Extended Abstract) | H. Raymond Strong |
| 1980 | The Node Cost Measure for Embedding Graphs on the Planar Grid (Extended Abstract) | James A. Storer |
| 1980 | A Complete Axiomatization for a Large Class of Dependencies in Relational Databases | Fereidoon Sadri, Jeffrey D. Ullman |
| 1980 | Random Matroids | John H. Reif, Paul G. Spirakis |
| 1980 | Logics for Probabilistic Programming (Extended Abstract) | John H. Reif |
| 1980 | Dynamic Algebras and the Nature of Induction | Vaughan R. Pratt |