| 1983 | Techniques for Solving Graph Problems in Parallel Environments | Peter H. Hochschild, Ernst W. Mayr, Alan R. Siegel |
| 1983 | Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report) | Juris Hartmanis |
| 1983 | Algebras of Feasible Functions | Yuri Gurevich |
| 1983 | A Kinetic Framework for Computational Geometry | Leonidas J. Guibas, Lyle Ramshaw, Jorge Stolfi |
| 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 | 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 | Tree Structures for Partial Match Retrieval | Philippe Flajolet, Claude Puech |
| 1983 | Probabilistic Counting | Philippe Flajolet, G. Nigel Martin |
| 1983 | On the Security of Multi-Party Ping-Pong Protocols | Shimon Even, Oded Goldreich |
| 1983 | Constructing Arrangements of Lines and Hyperplanes with Applications | Herbert Edelsbrunner, Joseph O'Rourke, Raimund Seidel |
| 1983 | On the Minimal Synchronism Needed for Distributed Consensus | Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer |
| 1983 | Geometric Retrieval Problems | Richard Cole, Chee-Keng Yap |
| 1983 | Fast Algorithms for the All Nearest Neighbors Problem | Kenneth L. Clarkson |
| 1983 | The Power of Geometric Duality | Bernard Chazelle, Leonidas J. Guibas, D. T. Lee |
| 1983 | Filtering Search: A New Approach to Query-Answering | Bernard Chazelle |
| 1983 | Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version) | Piotr Berman, Janos Simon |
| 1983 | On Context-Free Generators | Joffroy Beauquier, Franoise Gire |
| 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 | Computational Complexity and the Classification of Finite Simple Groups | Lszl Babai, William M. Kantor, Eugene M. Luks |
| 1983 | Dynamic Computational Geometry (Preliminary Version) | Mikhail J. Atallah |
| 1983 | Minimum Partition of Polygonal Regions into Trapezoids | Tetsuo Asano, Takao Asano |