| 1992 | A Class of Logic Problems Solvable by Linear Programming | Michele Conforti, Grard Cornujols |
| 1992 | Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract) | Richard Cole, Ramesh Hariharan |
| 1992 | Approximate Max Flow on Small Depth Networks | Edith Cohen |
| 1992 | Safe and Effective Determinant Evaluation | Kenneth L. Clarkson |
| 1992 | Mick Gets Some (the Odds Are on His Side) | Vasek Chvtal, Bruce A. Reed |
| 1992 | The Complexity of Parallel Prefix Problems on Small Domains | Shiva Chaudhuri, Jaikumar Radhakrishnan |
| 1992 | On the Completeness of Object-Creating Query Languages (Extended Abstract) | Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens |
| 1992 | Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues | Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan |
| 1992 | On the Exact Learning of Formulas in Parallel (Extended Abstract) | Nader H. Bshouty, Richard Cleve |
| 1992 | A Decomposition Theorem and Bounds for Randomized Server Problems | Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks |
| 1992 | Towards a Computational Theory of Statistical Tests (Extended Abstract) | Manuel Blum, Oded Goldreich |
| 1992 | How to Denest Ramanujan's Nested Radicals | Johannes Blmer |
| 1992 | Improved Parallel Polynomial Division and Its Extensions | Dario Bini, Victor Y. Pan |
| 1992 | The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms | Yair Bartal, Adi Rosn |
| 1992 | On-line Load Balancing (Extended Abstract) | Yossi Azar, Andrei Z. Broder, Anna R. Karlin |
| 1992 | Clock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation (Extended Abstract) | Yonatan Aumann, Michael O. Rabin |
| 1992 | Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor | James Aspnes, Orli Waarts |
| 1992 | Probabilistic Checking of Proofs; A New Characterization of NP | Sanjeev Arora, Shmuel Safra |
| 1992 | Proof Verification and Hardness of Approximation Problems | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy |
| 1992 | Reconstructing Algebraic Functions from Mixed Data | Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan |
| 1992 | Back to the Future: Towards a Theory of Timed Regular Languages | Rajeev Alur, Thomas A. Henzinger |
| 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 | Witnesses for Boolean Matrix Multiplication and for Shortest Paths | Noga Alon, Zvi Galil, Oded Margalit, Moni Naor |
| 1992 | The Algorithmic Aspects of the Regularity Lemma (Extended Abstract) | Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rdl, Raphael Yuster |
| 1992 | Halvers and Expanders | Mikls Ajtai, Jnos Komls, Endre Szemerdi |