| 1993 | Depth reduction for noncommutative arithmetic circuits. | Eric Allender, Jia Jiao |
| 1993 | Approximate load balancing on dynamic and asynchronous networks. | William Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao |
| 1992 | Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract) | Ramarathnam Venkatesan, Sivaramakrishnan Rajagopalan |
| 1992 | The History and Status of the P versus NP Question | Michael Sipser |
| 1992 | On the Complexity of RAM with Various Operation Sets | Janos Simon, Mario Szegedy |
| 1992 | On the All-Pairs-Shortest-Path Problem | Raimund Seidel |
| 1992 | Sample Spaces Uniform on Neighborhoods | Leonard J. Schulman |
| 1992 | Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract) | Shmuel Safra |
| 1992 | Finding Approximate Separators and Computing Tree Width Quickly | Bruce A. Reed |
| 1992 | Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract) | Satish Rao |
| 1992 | A Hypercubic Sorting Network with Nearly Logarithmic Depth | C. Greg Plaxton |
| 1992 | On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version) | Ramamohan Paturi |
| 1992 | Shallow Multiplication Circuits and Wise Financial Investments | Mike Paterson, Uri Zwick |
| 1992 | Improved Distributed Algorithms for Coloring and Network Decomposition Problems | Alessandro Panconesi, Aravind Srinivasan |
| 1992 | On the Degree of Boolean Functions as Real Polynomials | Noam Nisan, Mario Szegedy |
| 1992 | RL ⊆ SC | Noam Nisan |
| 1992 | Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract) | Alain J. Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung |
| 1992 | On the Angular Resolution of Planar Graphs | Seth M. Malitz, Achilleas Papakostas |
| 1992 | Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (Extended Abstract) | Bruce M. Maggs, Ramesh K. Sitaraman |
| 1992 | Ham-Sandwich Cuts in R^d | Chi-Yuan Lo, Jir Matousek, William L. Steiger |
| 1992 | epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract) | Jyh-Han Lin, Jeffrey Scott Vitter |
| 1992 | A Logspace Algorithm for Tree Canonization (Extended Abstract) | Steven Lindell |
| 1992 | Fault Tolerant Planar Communication Networks | Geng Lin |
| 1992 | Methods for Message Routing in Parallel Machines | Frank Thomson Leighton |
| 1992 | Online Minimization of Transition Systems (Extended Abstract) | David Lee, Mihalis Yannakakis |