| 1983 | 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983 |
| 1983 | A Kinetic Framework for Computational Geometry Leonidas J. Guibas, Lyle Ramshaw, Jorge Stolfi |
| 1983 | A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract) Mihalis Yannakakis |
| 1983 | A Tight Bound for Black and White Pebbles on the Pyramid Maria M. Klawe |
| 1983 | A Topological Approach to Evasiveness Jeff Kahn, Michael E. Saks, Dean Sturtevant |
| 1983 | Algebras of Feasible Functions Yuri Gurevich |
| 1983 | An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads (Extended Abstract) Brenda S. Baker, Ron Y. Pinter |
| 1983 | Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version) Brenda S. Baker |
| 1983 | Bin Packing with Items Uniformly Distributed over Intervals [a,b] George S. Lueker |
| 1983 | Computational Complexity and the Classification of Finite Simple Groups László Babai, William M. Kantor, Eugene M. Luks |
| 1983 | Constructing Arrangements of Lines and Hyperplanes with Applications Herbert Edelsbrunner, Joseph O'Rourke, Raimund Seidel |
| 1983 | Decision Procedures for Time and Chance (Extended Abstract) Sarit Kraus, Daniel Lehmann |
| 1983 | Dynamic Computational Geometry (Preliminary Version) Mikhail J. Atallah |
| 1983 | Estimating the Multiplicities of Conflicts in Multiple Access Channels (Preliminary Report) Albert G. Greenberg, Richard E. Ladner |
| 1983 | Factoring Sparse Multivariate Polynomials Joachim von zur Gathen |
| 1983 | Fast Algorithms for the All Nearest Neighbors Problem Kenneth L. Clarkson |
| 1983 | Filtering Search: A New Approach to Query-Answering Bernard Chazelle |
| 1983 | Games Against Nature (Extended Abstract) Christos H. Papadimitriou |
| 1983 | Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report) Juris Hartmanis |
| 1983 | Geometric Retrieval Problems Richard Cole, Chee-Keng Yap |
| 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 | Hash Functions for Priority Queues Miklós Ajtai, Michael L. Fredman, János Komlós |
| 1983 | How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin Michael Luby, Silvio Micali, Charles Rackoff |
| 1983 | Improved Upper Bounds on Shellsort Janet Incerpi, Robert Sedgewick |
| 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 | Logarithmic Depth Circuits for Algebraic Functions John H. Reif |
| 1983 | Lower Bounds by Probabilistic Arguments (Extended Abstract) Andrew Chi-Chih Yao |
| 1983 | Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version) Piotr Berman, Janos Simon |
| 1983 | Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version) Ramamohan Paturi, Janos Simon |
| 1983 | Minimum Partition of Polygonal Regions into Trapezoids Tetsuo Asano, Takao Asano |
| 1983 | Monte-Carlo Algorithms for Enumeration and Reliability Problems Richard M. Karp, Michael Luby |
| 1983 | Multiplication Is the Easiest Nontrivial Arithmetic Function Helmut Alt |
| 1983 | On Context-Free Generators Joffroy Beauquier, Françoise Gire |
| 1983 | On Depth-Reduction and Grates Georg Schnitger |
| 1983 | On Determinism versus Non-Determinism and Related Problems (Preliminary Version) Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter |
| 1983 | On the Computational Complexity of the Permanent (Extended Abstract) Joseph F. JáJá |
| 1983 | On the Minimal Synchronism Needed for Distributed Consensus Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer |
| 1983 | On the Security of Multi-Party Ping-Pong Protocols Shimon Even, Oded Goldreich |
| 1983 | Optimum Algorithms for Two Random Sampling Problems (Extended Abstract) Jeffrey Scott Vitter |
| 1983 | Partition of Planar Flow Networks (Preliminary Version) Donald B. Johnson, Shankar M. Venkatesan |
| 1983 | Period-Time Tradeoffs for VLSI Models with Delay (Preliminary Version) Alok Aggarwal |
| 1983 | Probabilistic Counting Philippe Flajolet, G. Nigel Martin |
| 1983 | Propositional Game Logic Rohit Parikh |
| 1983 | Randomized Byzantine Generals Michael O. Rabin |
| 1983 | Randomness and the Density of Hard Problems Robert E. Wilber |
| 1983 | Reasoning about Functional Programs and Complexity Classes Associated with Type Disciplines Daniel Leivant |
| 1983 | Reasoning about Infinite Computation Paths (Extended Abstract) Pierre Wolper, Moshe Y. Vardi, A. Prasad Sistla |
| 1983 | Relativized Circuit Complexity Christopher B. Wilson |
| 1983 | Representations of Rational Functions Joachim von zur Gathen |
| 1983 | Scaling Algorithms for Network Problems Harold N. Gabow |
| 1983 | Shortest Path Problems in Planar Graphs (Preliminary Version) Greg N. Frederickson |
| 1983 | Solving Low-Density Subset Sum Problems J. C. Lagarias, Andrew M. Odlyzko |
| 1983 | Some Relationships between Logics of Programs and Complexity Theory (Extended Abstract) Jerzy Tiuryn, Pawel Urzyczyn |
| 1983 | Techniques for Solving Graph Problems in Parallel Environments Peter H. Hochschild, Ernst W. Mayr, Alan R. Siegel |
| 1983 | The Parallel Complexity of the Abelian Permutation Group Membership Problem Pierre McKenzie, Stephen A. Cook |
| 1983 | The Power of Geometric Duality Bernard Chazelle, Leonidas J. Guibas, D. T. Lee |
| 1983 | The Program Complexity of Searching a Table Harry G. Mairson |
| 1983 | Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version) Uzi Vishkin, Avi Wigderson |
| 1983 | Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | Tree Structures for Partial Match Retrieval Philippe Flajolet, Claude Puech |