| 1992 | 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, October 24-27, 1992 |
| 1992 | A Class of Logic Problems Solvable by Linear Programming Michele Conforti, Gérard Cornuéjols |
| 1992 | A Decomposition Theorem and Bounds for Randomized Server Problems Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks |
| 1992 | A Mildly Exponential Approximation Algorithm for the Permanent Mark Jerrum, Umesh V. Vazirani |
| 1992 | A Subexponential Algorithm for Abstract Optimization Problems Bernd Gärtner |
| 1992 | A Theory of Wormhole Routing in Parallel Computers (Extended Abstract) Sergio A. Felperin, Prabhakar Raghavan, Eli Upfal |
| 1992 | Algebraic Decision Trees and Euler Characteristics Andrew Chi-Chih Yao |
| 1992 | Amplification and Percolation Moshe Dubiner, Uri Zwick |
| 1992 | Apple Tasting and Nearly One-Sided Learning David P. Helmbold, Nick Littlestone, Philip M. Long |
| 1992 | Approximate Max Flow on Small Depth Networks Edith Cohen |
| 1992 | Back to the Future: Towards a Theory of Timed Regular Languages Rajeev Alur, Thomas A. Henzinger |
| 1992 | Clock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation (Extended Abstract) Yonatan Aumann, Michael O. Rabin |
| 1992 | Communication on Noisy Channels: A Coding Theorem for Computation Leonard J. Schulman |
| 1992 | Competitive Analysis of Financial Games Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin |
| 1992 | Computing a Shortest k-Link Path in a Polygon Joseph S. B. Mitchell, Christine D. Piatko, Esther M. Arkin |
| 1992 | Computing in Solvable Matrix Groups Eugene M. Luks |
| 1992 | Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan |
| 1992 | Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract) Goos Kant |
| 1992 | Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees Pankaj K. Agarwal, David Eppstein, Jirí Matousek |
| 1992 | Efficient Inference of Partial Types Dexter Kozen, Jens Palsberg, Michael I. Schwartzbach |
| 1992 | Efficient Minimum Cost Matching Using Quadrangle Inequality Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber |
| 1992 | Efficient Self-Embedding of Butterfly Networks with Random Faults Hisao Tamaki |
| 1992 | Enumerating the k Closest Pairs Optimally Hans-Peter Lenhof, Michiel H. M. Smid |
| 1992 | Exact Analysis of Hot-Potato Routing (Extended Abstract) Uriel Feige, Prabhakar Raghavan |
| 1992 | Fast Algorithms for Matrix Normal Forms Mark Giesbrecht |
| 1992 | Fast Unimodular Reduction: Planar Integer Lattices (Extended Abstract) Chee-Keng Yap |
| 1992 | Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi |
| 1992 | Fault-tolerant Wait-free Shared Objects Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg |
| 1992 | Fully Dynamic Biconnectivity in Graphs Monika Rauch |
| 1992 | Halvers and Expanders Miklós Ajtai, János Komlós, Endre Szemerédi |
| 1992 | Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic Erich Grädel, Gregory L. McColm |
| 1992 | How to Denest Ramanujan's Nested Radicals Johannes Blömer |
| 1992 | Improved Lower Bounds for Shellsort C. Greg Plaxton, Bjorn Poonen, Torsten Suel |
| 1992 | Improved Parallel Polynomial Division and Its Extensions Dario Bini, Victor Y. Pan |
| 1992 | Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract) Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer |
| 1992 | Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary) Don Coppersmith, Baruch Schieber |
| 1992 | Markov Paging (Extended Abstract) Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan |
| 1992 | Maximizing Non-Linear Concave Functions in Fixed Dimension Sivan Toledo |
| 1992 | Mick Gets Some (the Odds Are on His Side) Vasek Chvátal, Bruce A. Reed |
| 1992 | Newton's Method for Fractional Combinatorial Optimization Tomasz Radzik |
| 1992 | On Efficient Band Matrix Arithmetic Wayne Eberly |
| 1992 | On Four-Connecting a Triconnected Graph (Extended Abstract) Tsan-sheng Hsu |
| 1992 | On Minimum and Maximum Spanning Trees of Linearly Moving Points Naoki Katoh, Takeshi Tokuyama, Kazuo Iwano |
| 1992 | On the Bit Extraction Problem Joel Friedman |
| 1992 | On the Completeness of Object-Creating Query Languages (Extended Abstract) Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens |
| 1992 | On the Exact Learning of Formulas in Parallel (Extended Abstract) Nader H. Bshouty, Richard Cleve |
| 1992 | On the Fault Tolerance of Some Popular Bounded-Degree Networks Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman |
| 1992 | On the Randomized Complexity of Volume and Diameter László Lovász, Miklós Simonovits |
| 1992 | On the Second Eigenvalue and Linear Expansion of Regular Graphs Nabil Kahalé |
| 1992 | On-line Load Balancing (Extended Abstract) Yossi Azar, Andrei Z. Broder, Anna R. Karlin |
| 1992 | Optimal Parallel Hull Construction for Simple Polygons in \calO(log log n) Time Hubert Wagener |
| 1992 | Probabilistic Checking of Proofs; A New Characterization of NP Sanjeev Arora, Shmuel Safra |
| 1992 | Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract) Erich L. Kaltofen, Victor Y. Pan |
| 1992 | Proof Verification and Hardness of Approximation Problems Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy |
| 1992 | Quadratic Dynamical Systems (Preliminary Version) Yuri Rabinovich, Alistair Sinclair, Avi Wigderson |
| 1992 | Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor James Aspnes, Orli Waarts |
| 1992 | Randomized Geometric Algorithms and Pseudo-Random Generators (Extended Abstract) Ketan Mulmuley |
| 1992 | Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries Howard Aizenstein, Lisa Hellerstein, Leonard Pitt |
| 1992 | Reconstructing Algebraic Functions from Mixed Data Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan |
| 1992 | Safe and Effective Determinant Evaluation Kenneth L. Clarkson |
| 1992 | Separating the Communication Complexities of MOD m and MOD p Circuits Vince Grolmusz |
| 1992 | Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract) David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig |
| 1992 | The Algorithmic Aspects of the Regularity Lemma (Extended Abstract) Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rödl, Raphael Yuster |
| 1992 | The Asymptotic Complexity of Merging Networks Peter Bro Miltersen, Mike Paterson, Jun Tarui |
| 1992 | The Complexity of Parallel Prefix Problems on Small Domains Shiva Chaudhuri, Jaikumar Radhakrishnan |
| 1992 | The Complexity of the Hajós Calculus Toniann Pitassi, Alasdair Urquhart |
| 1992 | The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms Yair Bartal, Adi Rosén |
| 1992 | The Isomorphism Conjecture Holds Relative to an Oracle Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz |
| 1992 | The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms Victor Y. Pan, John H. Reif, Stephen R. Tate |
| 1992 | Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract) Richard Cole, Ramesh Hariharan |
| 1992 | Tiling a Polygon with Rectangles Claire Kenyon, Richard W. Kenyon |
| 1992 | Towards a Computational Theory of Statistical Tests (Extended Abstract) Manuel Blum, Oded Goldreich |
| 1992 | Truly Alphabet-Independent Two-Dimensional Pattern Matching Zvi Galil, Kunsoo Park |
| 1992 | Undecidability of the Horn-Clause Implication Problem Jerzy Marcinkowski, Leszek Pacholski |
| 1992 | Undirected Connectivity in O(log ^1.5 n) Space Noam Nisan, Endre Szemerédi, Avi Wigderson |
| 1992 | Waste Makes Haste: Tight Bounds for Loose Parallel Sorting Torben Hagerup, Rajeev Raman |
| 1992 | Witnesses for Boolean Matrix Multiplication and for Shortest Paths Noga Alon, Zvi Galil, Oded Margalit, Moni Naor |
| 1992 | Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract) Alfredo De Santis, Giuseppe Persiano |