| 1992 | Small-Depth Counting Networks | Michael Klugerman, C. Greg Plaxton |
| 1992 | A Parallel Randomized Approximation Scheme for Shortest Paths | Philip N. Klein, Sairam Sairam |
| 1992 | A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract) | Joe Kilian |
| 1992 | Biconnectivity Approximations and Graph Carvings | Samir Khuller, Uzi Vishkin |
| 1992 | On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph | Pierre Kelsen |
| 1992 | Efficient Program Transformations for Resilient Parallel Computation via Randomization (Preliminary Version) | Zvi M. Kedem, Krishna V. Palem, Michael O. Rabin, A. Raghunathan |
| 1992 | Efficient PRAM Simulation on a Distributed Memory Machine | Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide |
| 1992 | A Subexponential Randomized Simplex Algorithm (Extended Abstract) | Gil Kalai |
| 1992 | Entropy and Sorting | Jeff Kahn, Jeong Han Kim |
| 1992 | Asymptotic Conditional Probabilities for First-Order Logic | Adam J. Grove, Joseph Y. Halpern, Daphne Koller |
| 1992 | Planar Separators and Parallel Polygon Triangulation (Preliminary Version) | Michael T. Goodrich |
| 1992 | Computing Frobenius Maps and Factoring Polynomials (Extended Abstract) | Joachim von zur Gathen, Victor Shoup |
| 1992 | Fully Dynamic Planarity Testing (Extended Abstract) | Zvi Galil, Giuseppe F. Italiano, Neil Sarnak |
| 1992 | A Constant-Time Optimal Parallel String-Matching Algorithm | Zvi Galil |
| 1992 | Communication Complexity of Secure Computation (Extended Abstract) | Matthew K. Franklin, Moti Yung |
| 1992 | Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract) | Uriel Feige, Lszl Lovsz |
| 1992 | On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract) | Uriel Feige, Carsten Lund |
| 1992 | Balanced Matroids | Toms Feder, Milena Mihail |
| 1992 | Approximations of General Independent Distributions | Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic |
| 1992 | Simple and Efficient Bounded Concurrent Timestamping or Bounded Concurrent Timestamp Systems are Comprehensible! | Cynthia Dwork, Orli Waarts |
| 1992 | Graph Decomposition Is NPC-A Complete Proof of Holyer's Conjecture | Dorit Dor, Michael Tarsi |
| 1992 | The Complexity of Multiway Cuts (Extended Abstract) | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
| 1992 | Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems | Manhoi Choy, Ambuj K. Singh |
| 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 | Parallel Computation Over Hyperbolic Groups | Jin-yi Cai |