| 1983 | The Complexity of Approximate Counting (Preliminary Version) | Larry J. Stockmeyer |
| 1983 | Transitive Orientation in O(n²) Time | Jeremy P. Spinrad |
| 1983 | Self-Adjusting Binary Trees | Daniel Dominic Sleator, Robert Endre Tarjan |
| 1983 | A Complexity Theoretic Approach to Randomness | Michael Sipser |
| 1983 | Borel Sets and Circuit Complexity | Michael Sipser |
| 1983 | A Logarithmic Time Sort for Linear Size Networks | John H. Reif, Leslie G. Valiant |
| 1983 | On the Extremely Fair Treatment of Probabilistic Algorithms | Amir Pnueli |
| 1983 | A Characterization of Hoare's Logic for Programs with Pascal-like Procedures | Ernst-Rdiger Olderog |
| 1983 | Retraction: A New Approach to Motion-Planning (Extended Abstract) | Colm 'Dnlaing, Micha Sharir, Chee-Keng Yap |
| 1983 | The Random Access Hierarchy (Preliminary Report) | Dale Myers |
| 1983 | How Discreet is the Discrete Log? | Douglas L. Long, Avi Wigderson |
| 1983 | Factoring Multivariate Polynomials over Finite Fields (Extended Abstract) | Arjen K. Lenstra |
| 1983 | Solvability by Radicals is in Polynomial Time | Susan Landau, Gary L. Miller |
| 1983 | A Probabilistic PDL | Dexter Kozen |
| 1983 | Alternation and the Power of Nondeterminism | Ravi Kannan |
| 1983 | Improved Algorithms for Integer Programming and Related Lattice Problems | Ravi Kannan |
| 1983 | Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract) | Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi |
| 1983 | Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication | Kazuo Iwama |
| 1983 | Languages Which Capture Complexity Classes (Preliminary Report) | Neil Immerman |
| 1983 | A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem | Friedhelm Meyer auf der Heide |
| 1983 | Sparse Sets in NP-P: EXPTIME versus NEXPTIME | Juris Hartmanis, Vivian Sewelson, Neil Immerman |
| 1983 | A Logic to Reason about Likelihood | Joseph Y. Halpern, Michael O. Rabin |
| 1983 | Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams | Leonidas J. Guibas, Jorge Stolfi |
| 1983 | Strong Signature Schemes | Shafi Goldwasser, Silvio Micali, Andrew Chi-Chih Yao |
| 1983 | Parallel algorithms for algebraic problems | Joachim von zur Gathen |