| 1992 | Learning Arithmetic Read-Once Formulas | Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein |
| 1992 | Existence and Construction of Edge Disjoint Paths on Expander Graphs | Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1992 | Target Shooting with Programmed Random Variables | Graham R. Brightwell, Teunis J. Ott, Peter Winkler |
| 1992 | Fast Learning of k-Term DNF Formulas with Queries | Avrim Blum, Steven Rudich |
| 1992 | Linear Decision Trees: Volume Estimates and Topological Bounds | Anders Bjrner, Lszl Lovsz, Andrew Chi-Chih Yao |
| 1992 | Can Finite Samples Detect Singularities of Real-Valued Functions? | Shai Ben-David |
| 1992 | Making Zero-Knowledge Provers Efficient | Mihir Bellare, Erez Petrank |
| 1992 | A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract) | Stephen J. Bellantoni, Stephen A. Cook |
| 1992 | When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One | Richard Beigel |
| 1992 | Randomized versus Nondeterministic Communication Complexity | Paul Beame, Joan Lawry |
| 1992 | Exponential Lower Bounds for the Pigeonhole Principle | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk, Alan R. Woods |
| 1992 | Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time | Robert Beals, kos Seress |
| 1992 | Feasibility Testing for Systems of Real Quadratic Equations | Alexander I. Barvinok |
| 1992 | Competitive Algorithms for Distributed Data Management (Extended Abstract) | Yair Bartal, Amos Fiat, Yuval Rabani |
| 1992 | New Algorithms for an Ancient Scheduling Problem | Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra |
| 1992 | Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) | David A. Mix Barrington, Richard Beigel, Steven Rudich |
| 1992 | Symmetry and Complexity | Lszl Babai, Robert Beals, Pl Takcsi-Nagy |
| 1992 | Biased Random Walks | Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips |
| 1992 | Adapting to Asynchronous Dynamic Networks (Extended Abstract) | Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks |
| 1992 | Competitive Distributed Job Scheduling (Extended Abstract) | Baruch Awerbuch, Shay Kutten, David Peleg |
| 1992 | Computing with Faulty Arrays | Yonatan Aumann, Michael Ben-Or |
| 1992 | A Correctness Condition for High-Performance Multiprocessors (Extended Abstract) | Hagit Attiya, Roy Friedman |
| 1992 | Computational Learning Theory: Survey and Selected Bibliography | Dana Angluin |
| 1992 | Alphabet Independent Two Dimensional Matching | Amihood Amir, Gary Benson, Martin Farach |
| 1992 | A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension | Mikls Ajtai, Nimrod Megiddo |