| 1994 | Lower bounds for parallel linear programming and other problems. | Ketan Mulmuley |
| 1994 | Lower bounds for union-split-find related problems on random access machines. | Peter Bro Miltersen |
| 1994 | Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version). | Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan |
| 1994 | Trade-offs between communication throughput and parallel time. | Yishay Mansour, Noam Nisan, Uzi Vishkin |
| 1994 | The computational complexity of recognizing permutation functions. | Keju Ma, Joachim von zur Gathen |
| 1994 | On contention resolution protocols and associated probabilistic phenomena. | Philip D. MacKenzie, C. Greg Plaxton, Rajmohan Rajaraman |
| 1994 | Simple strategies for large zero-sum games with applications to complexity theory. | Richard J. Lipton, Neal E. Young |
| 1994 | The complexity of verification. | Robert P. Kurshan |
| 1994 | On the computational power of depth 2 circuits with threshold and modulo gates. | Matthias Krause, Pavel Pudlk |
| 1994 | On the | Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version). | S. Rao Kosaraju |
| 1994 | Fast algorithms for finding randomized strategies in game trees. | Daphne Koller, Nimrod Megiddo, Bernhard von Stengel |
| 1994 | A randomized linear-time algorithm for finding minimum spanning trees. | Philip N. Klein, Robert Endre Tarjan |
| 1994 | Faster shortest-path algorithms for planar graphs. | Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian |
| 1994 | Low degree spanning trees of small weight. | Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 1994 | On the learnability of discrete distributions. | Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie |
| 1994 | On construction of | Howard J. Karloff, Yishay Mansour |
| 1994 | On the fault tolerance of the butterfly. | Anna R. Karlin, Greg Nelson, Hisao Tamaki |
| 1994 | Derandomization through approximation: an | David R. Karger, Rajeev Motwani |
| 1994 | Random sampling in cut, flow, and network design problems. | David R. Karger |
| 1994 | Fault-tolerant scheduling. | Bala Kalyanasundaram, Kirk Pruhs |
| 1994 | Two heads are better than two tapes. | Tao Jiang, Joel I. Seiferas, Paul M. B. Vitnyi |
| 1994 | Aligning sequences via an evolutionary tree: complexity and approximation. | Tao Jiang, Eugene L. Lawler, Lusheng Wang |
| 1994 | Circuit complexity: from the worst case to the average case. | Andreas Jakoby, Rdiger Reischuk, Christian Schindelhauer |
| 1994 | A functional equation often arising in the analysis of algorithms (extended abstract). | Philippe Jacquet, Wojciech Szpankowski |