| 1983 | Reliable Computation with Cellular Automata | Pter Gcs |
| 1983 | A Linear-Time Algorithm for a Special Case of Disjoint Set Union | Harold N. Gabow, Robert Endre Tarjan |
| 1983 | An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems | Harold N. Gabow |
| 1983 | Normal Forms for Trivalent Graphs and Graphs of Bounded Valence | Martin Frer, Walter Schnyder, Ernst Specker |
| 1983 | Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version) | Greg N. Frederickson |
| 1983 | New Bounds for Parallel Prefix Circuits | Faith E. Fich |
| 1983 | A Decidable Propositional Probabilistic Dynamic Logic | Yishai A. Feldman |
| 1983 | Iterated Pushdown Automata and Complexity Classes | Joost Engelfriet |
| 1983 | Speedups of Deterministic Machines by Synchronous Parallel Machines | Patrick W. Dymond, Martin Tompa |
| 1983 | Two Nonlinear Lower Bounds | Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rdiger Reischuk |
| 1983 | On the Diameter of Permutation Groups | James R. Driscoll, Merrick L. Furst |
| 1983 | Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version) | Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson |
| 1983 | Multi-Party Protocols | Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton |
| 1983 | Unbounded Fan-in Circuits and Associative Functions | Ashok K. Chandra, Steven Fortune, Richard J. Lipton |
| 1983 | Bounds for Width Two Branching Programs | Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul |
| 1983 | How to Exchange (Secret) Keys (Extended Abstract) | Manuel Blum |
| 1983 | On the Cryptographic Security of Single RSA Bits | Michael Ben-Or, Benny Chor, Adi Shamir |
| 1983 | Lower Bounds for Algebraic Computation Trees (Preliminary Report) | Michael Ben-Or |
| 1983 | An Approximation Algorithm for Manhattan Routing (Extended Abstract) | Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton |
| 1983 | How to Generate Random Integers with Known Factorization | Eric Bach |
| 1983 | Canonical Labeling of Graphs | Lszl Babai, Eugene M. Luks |
| 1983 | An O(n log n) Sorting Network | Mikls Ajtai, Jnos Komls, Endre Szemerdi |
| 1983 | On Notions of Information Transfer in VLSI Circuits | Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis |
| 1983 | On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract) | Leonard M. Adleman |
| 1982 | Space-Time Tradeoff for Answering Range Queries (Extended Abstract) | Andrew Chi-Chih Yao |