| 1983 | Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design | Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | Some Relationships between Logics of Programs and Complexity Theory (Extended Abstract) | Jerzy Tiuryn, Pawel Urzyczyn |
| 1983 | On Depth-Reduction and Grates | Georg Schnitger |
| 1983 | Logarithmic Depth Circuits for Algebraic Functions | John H. Reif |
| 1983 | Randomized Byzantine Generals | Michael O. Rabin |
| 1983 | On Determinism versus Non-Determinism and Related Problems (Preliminary Version) | Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerdi, William T. Trotter |
| 1983 | Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version) | Ramamohan Paturi, Janos Simon |
| 1983 | Propositional Game Logic | Rohit Parikh |
| 1983 | Games Against Nature (Extended Abstract) | Christos H. Papadimitriou |
| 1983 | The Parallel Complexity of the Abelian Permutation Group Membership Problem | Pierre McKenzie, Stephen A. Cook |
| 1983 | The Program Complexity of Searching a Table | Harry G. Mairson |
| 1983 | Bin Packing with Items Uniformly Distributed over Intervals [a,b] | George S. Lueker |
| 1983 | How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin | Michael Luby, Silvio Micali, Charles Rackoff |
| 1983 | Information Bounds Are Good for Search Problems on Ordered Data Structures | Nathan Linial, Michael E. Saks |
| 1983 | Legal Coloring of Graphs | Nathan Linial |
| 1983 | Reasoning about Functional Programs and Complexity Classes Associated with Type Disciplines | Daniel Leivant |
| 1983 | Solving Low-Density Subset Sum Problems | J. C. Lagarias, Andrew M. Odlyzko |
| 1983 | Decision Procedures for Time and Chance (Extended Abstract) | Sarit Kraus, Daniel Lehmann |
| 1983 | A Tight Bound for Black and White Pebbles on the Pyramid | Maria M. Klawe |
| 1983 | Global Wire Routing in Two-Dimensional Arrays (Extended Abstract) | Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | Monte-Carlo Algorithms for Enumeration and Reliability Problems | Richard M. Karp, Michael Luby |
| 1983 | A Topological Approach to Evasiveness | Jeff Kahn, Michael E. Saks, Dean Sturtevant |
| 1983 | Partition of Planar Flow Networks (Preliminary Version) | Donald B. Johnson, Shankar M. Venkatesan |
| 1983 | On the Computational Complexity of the Permanent (Extended Abstract) | Joseph F. JJ |
| 1983 | Improved Upper Bounds on Shellsort | Janet Incerpi, Robert Sedgewick |