| 1992 | A Constant-Time Optimal Parallel String-Matching Algorithm Zvi Galil |
| 1992 | A Correctness Condition for High-Performance Multiprocessors (Extended Abstract) Hagit Attiya, Roy Friedman |
| 1992 | A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields (Preliminary Version) Paul B. Callahan, S. Rao Kosaraju |
| 1992 | A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension Miklós Ajtai, Nimrod Megiddo |
| 1992 | A Hypercubic Sorting Network with Nearly Logarithmic Depth C. Greg Plaxton |
| 1992 | A Logspace Algorithm for Tree Canonization (Extended Abstract) Steven Lindell |
| 1992 | A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract) Stephen J. Bellantoni, Stephen A. Cook |
| 1992 | A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract) Joe Kilian |
| 1992 | A Parallel Randomized Approximation Scheme for Shortest Paths Philip N. Klein, Sairam Sairam |
| 1992 | A Subexponential Randomized Simplex Algorithm (Extended Abstract) Gil Kalai |
| 1992 | Adapting to Asynchronous Dynamic Networks (Extended Abstract) Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks |
| 1992 | Alphabet Independent Two Dimensional Matching Amihood Amir, Gary Benson, Martin Farach |
| 1992 | Approximations of General Independent Distributions Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic |
| 1992 | Asymptotic Conditional Probabilities for First-Order Logic Adam J. Grove, Joseph Y. Halpern, Daphne Koller |
| 1992 | Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract) Ramarathnam Venkatesan, Sivaramakrishnan Rajagopalan |
| 1992 | Balanced Matroids Tomás Feder, Milena Mihail |
| 1992 | Biased Random Walks Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips |
| 1992 | Biconnectivity Approximations and Graph Carvings Samir Khuller, Uzi Vishkin |
| 1992 | Can Finite Samples Detect Singularities of Real-Valued Functions? Shai Ben-David |
| 1992 | Communication Complexity of Secure Computation (Extended Abstract) Matthew K. Franklin, Moti Yung |
| 1992 | Competitive Algorithms for Distributed Data Management (Extended Abstract) Yair Bartal, Amos Fiat, Yuval Rabani |
| 1992 | Competitive Distributed Job Scheduling (Extended Abstract) Baruch Awerbuch, Shay Kutten, David Peleg |
| 1992 | Computational Learning Theory: Survey and Selected Bibliography Dana Angluin |
| 1992 | Computing Frobenius Maps and Factoring Polynomials (Extended Abstract) Joachim von zur Gathen, Victor Shoup |
| 1992 | Computing with Faulty Arrays Yonatan Aumann, Michael Ben-Or |
| 1992 | Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems Manhoi Choy, Ambuj K. Singh |
| 1992 | Efficient PRAM Simulation on a Distributed Memory Machine Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide |
| 1992 | Efficient Program Transformations for Resilient Parallel Computation via Randomization (Preliminary Version) Zvi M. Kedem, Krishna V. Palem, Michael O. Rabin, A. Raghunathan |
| 1992 | Entropy and Sorting Jeff Kahn, Jeong Han Kim |
| 1992 | Existence and Construction of Edge Disjoint Paths on Expander Graphs Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1992 | Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract) Shmuel Safra |
| 1992 | Exponential Lower Bounds for the Pigeonhole Principle Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods |
| 1992 | Fast Learning of k-Term DNF Formulas with Queries Avrim Blum, Steven Rudich |
| 1992 | Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract) Satish Rao |
| 1992 | Fault Tolerant Planar Communication Networks Geng Lin |
| 1992 | Feasibility Testing for Systems of Real Quadratic Equations Alexander I. Barvinok |
| 1992 | Finding Approximate Separators and Computing Tree Width Quickly Bruce A. Reed |
| 1992 | Fully Dynamic Planarity Testing (Extended Abstract) Zvi Galil, Giuseppe F. Italiano, Neil Sarnak |
| 1992 | Graph Decomposition Is NPC-A Complete Proof of Holyer's Conjecture Dorit Dor, Michael Tarsi |
| 1992 | Ham-Sandwich Cuts in R^d Chi-Yuan Lo, Jirí Matousek, William L. Steiger |
| 1992 | Improved Distributed Algorithms for Coloring and Network Decomposition Problems Alessandro Panconesi, Aravind Srinivasan |
| 1992 | Learning Arithmetic Read-Once Formulas Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein |
| 1992 | Linear Decision Trees: Volume Estimates and Topological Bounds Anders Björner, László Lovász, Andrew Chi-Chih Yao |
| 1992 | Making Zero-Knowledge Provers Efficient Mihir Bellare, Erez Petrank |
| 1992 | Methods for Message Routing in Parallel Machines Frank Thomson Leighton |
| 1992 | New Algorithms for an Ancient Scheduling Problem Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra |
| 1992 | On the All-Pairs-Shortest-Path Problem Raimund Seidel |
| 1992 | On the Angular Resolution of Planar Graphs Seth M. Malitz, Achilleas Papakostas |
| 1992 | On the Complexity of RAM with Various Operation Sets Janos Simon, Mario Szegedy |
| 1992 | On the Degree of Boolean Functions as Real Polynomials Noam Nisan, Mario Szegedy |
| 1992 | On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version) Ramamohan Paturi |
| 1992 | On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract) Uriel Feige, Carsten Lund |
| 1992 | On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph Pierre Kelsen |
| 1992 | Online Minimization of Transition Systems (Extended Abstract) David Lee, Mihalis Yannakakis |
| 1992 | Parallel Computation Over Hyperbolic Groups Jin-Yi Cai |
| 1992 | Planar Separators and Parallel Polygon Triangulation (Preliminary Version) Michael T. Goodrich |
| 1992 | Polynomial Algorithms for Linear Programming over the Algebraic Numbers Ilan Adler, Peter A. Beling |
| 1992 | Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada S. Rao Kosaraju, Mike Fellows, Avi Wigderson, John A. Ellis |
| 1992 | RL ⊆ SC Noam Nisan |
| 1992 | Randomized versus Nondeterministic Communication Complexity Paul Beame, Joan Lawry |
| 1992 | Ray Shooting and Parametric Search Pankaj K. Agarwal, Jirí Matousek |
| 1992 | Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) David A. Mix Barrington, Richard Beigel, Steven Rudich |
| 1992 | Sample Spaces Uniform on Neighborhoods Leonard J. Schulman |
| 1992 | Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract) Alain J. Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung |
| 1992 | Shallow Multiplication Circuits and Wise Financial Investments Mike Paterson, Uri Zwick |
| 1992 | Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (Extended Abstract) Bruce M. Maggs, Ramesh K. Sitaraman |
| 1992 | Simple and Efficient Bounded Concurrent Timestamping or Bounded Concurrent Timestamp Systems are Comprehensible! Cynthia Dwork, Orli Waarts |
| 1992 | Small-Depth Counting Networks Michael Klugerman, C. Greg Plaxton |
| 1992 | Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time Robert Beals, Ákos Seress |
| 1992 | Symmetry and Complexity László Babai, Robert Beals, Pál Takácsi-Nagy |
| 1992 | Target Shooting with Programmed Random Variables Graham R. Brightwell, Teunis J. Ott, Peter Winkler |
| 1992 | The Complexity of Multiway Cuts (Extended Abstract) Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
| 1992 | The History and Status of the P versus NP Question Michael Sipser |
| 1992 | Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract) Uriel Feige, László Lovász |
| 1992 | When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One Richard Beigel |
| 1992 | epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract) Jyh-Han Lin, Jeffrey Scott Vitter |