| 1992 | Tiling a Polygon with Rectangles | Claire Kenyon, Richard W. Kenyon |
| 1992 | On Minimum and Maximum Spanning Trees of Linearly Moving Points | Naoki Katoh, Takeshi Tokuyama, Kazuo Iwano |
| 1992 | Markov Paging (Extended Abstract) | Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan |
| 1992 | Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract) | Goos Kant |
| 1992 | Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract) | Erich L. Kaltofen, Victor Y. Pan |
| 1992 | On the Second Eigenvalue and Linear Expansion of Regular Graphs | Nabil Kahal |
| 1992 | A Mildly Exponential Approximation Algorithm for the Permanent | Mark Jerrum, Umesh V. Vazirani |
| 1992 | Fault-tolerant Wait-free Shared Objects | Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg |
| 1992 | On Four-Connecting a Triconnected Graph (Extended Abstract) | Tsan-sheng Hsu |
| 1992 | Apple Tasting and Nearly One-Sided Learning | David P. Helmbold, Nick Littlestone, Philip M. Long |
| 1992 | Waste Makes Haste: Tight Bounds for Loose Parallel Sorting | Torben Hagerup, Rajeev Raman |
| 1992 | Separating the Communication Complexities of MOD m and MOD p Circuits | Vince Grolmusz |
| 1992 | Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic | Erich Grdel, Gregory L. McColm |
| 1992 | Fast Algorithms for Matrix Normal Forms | Mark Giesbrecht |
| 1992 | A Subexponential Algorithm for Abstract Optimization Problems | Bernd Grtner |
| 1992 | Truly Alphabet-Independent Two-Dimensional Pattern Matching | Zvi Galil, Kunsoo Park |
| 1992 | On the Bit Extraction Problem | Joel Friedman |
| 1992 | The Isomorphism Conjecture Holds Relative to an Oracle | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz |
| 1992 | A Theory of Wormhole Routing in Parallel Computers (Extended Abstract) | Sergio A. Felperin, Prabhakar Raghavan, Eli Upfal |
| 1992 | Exact Analysis of Hot-Potato Routing (Extended Abstract) | Uriel Feige, Prabhakar Raghavan |
| 1992 | Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract) | David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig |
| 1992 | Competitive Analysis of Financial Games | Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin |
| 1992 | On Efficient Band Matrix Arithmetic | Wayne Eberly |
| 1992 | Amplification and Percolation | Moshe Dubiner, Uri Zwick |
| 1992 | Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary) | Don Coppersmith, Baruch Schieber |