| 1983 | A 3-Space Partition and Its Applications (Extended Abstract) F. Frances Yao |
| 1983 | A Characterization of Hoare's Logic for Programs with Pascal-like Procedures Ernst-Rüdiger Olderog |
| 1983 | A Complexity Theoretic Approach to Randomness Michael Sipser |
| 1983 | A Decidable Propositional Probabilistic Dynamic Logic Yishai A. Feldman |
| 1983 | A Linear-Time Algorithm for a Special Case of Disjoint Set Union Harold N. Gabow, Robert Endre Tarjan |
| 1983 | A Logarithmic Time Sort for Linear Size Networks John H. Reif, Leslie G. Valiant |
| 1983 | A Logic to Reason about Likelihood Joseph Y. Halpern, Michael O. Rabin |
| 1983 | A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem Friedhelm Meyer auf der Heide |
| 1983 | A Probabilistic PDL Dexter Kozen |
| 1983 | Alternation and the Power of Nondeterminism Ravi Kannan |
| 1983 | An Approximation Algorithm for Manhattan Routing (Extended Abstract) Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton |
| 1983 | An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems Harold N. Gabow |
| 1983 | An O(n log n) Sorting Network Miklós Ajtai, János Komlós, Endre Szemerédi |
| 1983 | Borel Sets and Circuit Complexity Michael Sipser |
| 1983 | Bounds for Width Two Branching Programs Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul |
| 1983 | Canonical Labeling of Graphs László Babai, Eugene M. Luks |
| 1983 | Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version) Greg N. Frederickson |
| 1983 | Exponential Lower Bounds for Restricted Monotone Circuits Leslie G. Valiant |
| 1983 | Factoring Multivariate Polynomials over Finite Fields (Extended Abstract) Arjen K. Lenstra |
| 1983 | How Discreet is the Discrete Log? Douglas L. Long, Avi Wigderson |
| 1983 | How to Exchange (Secret) Keys (Extended Abstract) Manuel Blum |
| 1983 | How to Generate Random Integers with Known Factorization Eric Bach |
| 1983 | Improved Algorithms for Integer Programming and Related Lattice Problems Ravi Kannan |
| 1983 | Iterated Pushdown Automata and Complexity Classes Joost Engelfriet |
| 1983 | Languages Which Capture Complexity Classes (Preliminary Report) Neil Immerman |
| 1983 | Lower Bounds for Algebraic Computation Trees (Preliminary Report) Michael Ben-Or |
| 1983 | Multi-Party Protocols Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton |
| 1983 | New Bounds for Parallel Prefix Circuits Faith E. Fich |
| 1983 | Normal Forms for Trivalent Graphs and Graphs of Bounded Valence Martin Fürer, Walter Schnyder, Ernst Specker |
| 1983 | On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract) Leonard M. Adleman |
| 1983 | On Notions of Information Transfer in VLSI Circuits Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1983 | On the Cryptographic Security of Single RSA Bits Michael Ben-Or, Benny Chor, Adi Shamir |
| 1983 | On the Diameter of Permutation Groups James R. Driscoll, Merrick L. Furst |
| 1983 | On the Extremely Fair Treatment of Probabilistic Algorithms Amir Pnueli |
| 1983 | Parallel algorithms for algebraic problems Joachim von zur Gathen |
| 1983 | Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams Leonidas J. Guibas, Jorge Stolfi |
| 1983 | Probabilistic Analysis of Bandwidth Minimization Algorithms Jonathan S. Turner |
| 1983 | Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas |
| 1983 | Reliable Computation with Cellular Automata Péter Gács |
| 1983 | Retraction: A New Approach to Motion-Planning (Extended Abstract) Colm Ó'Dúnlaing, Micha Sharir, Chee-Keng Yap |
| 1983 | Self-Adjusting Binary Trees Daniel Dominic Sleator, Robert Endre Tarjan |
| 1983 | Solvability by Radicals is in Polynomial Time Susan Landau, Gary L. Miller |
| 1983 | Some Structural Properties of Polynomial Reducibilities and Sets in NP Paul Young |
| 1983 | Sparse Sets in NP-P: EXPTIME versus NEXPTIME Juris Hartmanis, Vivian Sewelson, Neil Immerman |
| 1983 | Speedups of Deterministic Machines by Synchronous Parallel Machines Patrick W. Dymond, Martin Tompa |
| 1983 | Strong Signature Schemes Shafi Goldwasser, Silvio Micali, Andrew Chi-Chih Yao |
| 1983 | Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version) Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson |
| 1983 | The Complexity of Approximate Counting (Preliminary Version) Larry J. Stockmeyer |
| 1983 | The Random Access Hierarchy (Preliminary Report) Dale Myers |
| 1983 | Topological Matching Quentin F. Stout |
| 1983 | Transitive Orientation in O(n²) Time Jeremy P. Spinrad |
| 1983 | Two Nonlinear Lower Bounds Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk |
| 1983 | Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract) Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi |
| 1983 | Unbounded Fan-in Circuits and Associative Functions Ashok K. Chandra, Steven Fortune, Richard J. Lipton |
| 1983 | Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication Kazuo Iwama |