| 1994 | Priority Encoding Transmission | Andres Albanese, Johannes Blmer, Jeff Edmonds, Michael Luby, Madhu Sudan |
| 1994 | A Theory of Competitive Analysis for Distributed Algorithms | Mikls Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
| 1994 | Algorithmic Number Theory-The Complexity Contribution | Leonard M. Adleman |
| 1993 | Quantum Circuit Complexity | Andrew Chi-Chih Yao |
| 1993 | Approximating Shortest Superstrings | Shang-Hua Teng, F. Frances Yao |
| 1993 | On Representations by Low-Degree Polynomials | Roman Smolensky |
| 1993 | Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions | Micha Sharir |
| 1993 | The NC Equivalence of Planar Integer Linear Programming and Euclidean GCD | David Shallcross, Victor Y. Pan, Yu Lin-Kriz |
| 1993 | An O(n log ^3 n) Algorithm for the Real Root Problem | John H. Reif |
| 1993 | On the "log rank"-Conjecture in Communication Complexity | Ran Raz, Boris Spieker |
| 1993 | Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs | Sridhar Rajagopalan, Vijay V. Vazirani |
| 1993 | Faster Algorithms for the Generalized Network Flow Problem | Tomasz Radzik |
| 1993 | Space Bounds for Graph Connectivity Problems on Node-named JAGs and Node-ordered JAGs | Chung Keung Poon |
| 1993 | Refining a Triangulation of a Planar Straight-Line Graph to Eliminate Large Angles | Scott A. Mitchell |
| 1993 | A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane | Michael McAllister, David G. Kirkpatrick, Jack Snoeyink |
| 1993 | Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract) | Charles E. Leiserson, Satish Rao, Sivan Toledo |
| 1993 | Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract) | Frank Thomson Leighton, Yuan Ma |
| 1993 | On Choosing a Dense Subgraph (Extended Abstract) | Guy Kortsarz, David Peleg |
| 1993 | A Weak Version of the Blum, Shub & Smale model | Pascal Koiran |
| 1993 | A linear-processor polylog-time algorithm for shortest paths in planar graphs | Philip N. Klein, Sairam Subramanian |
| 1993 | Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees | David R. Karger |
| 1993 | Universal Emulations with Sublogarithmic Slowdown | Christos Kaklamanis, Danny Krizanc, Satish Rao |
| 1993 | The Complexity and Distribution of Hard Problems (Extended Abstract) | David W. Juedes, Jack H. Lutz |
| 1993 | Simulated Annealing for Graph Bisection | Mark Jerrum, Gregory B. Sorkin |
| 1993 | On the Value of Information in Coordination Games (preliminary version) | Sandy Irani, Yuval Rabani |