| 1994 | Pseudorandomness for network algorithms. | Russell Impagliazzo, Noam Nisan, Avi Wigderson |
| 1994 | A simple constructive computability theorem for wait-free computation. | Maurice Herlihy, Nir Shavit |
| 1994 | Optimal parallel suffix tree construction. | Ramesh Hariharan |
| 1994 | Greed is good: approximating independent sets in sparse and bounded-degree graphs. | Magns M. Halldrsson, Jaikumar Radhakrishnan |
| 1994 | Optimal parallel string algorithms: sorting, merging and computing the minimum. | Torben Hagerup |
| 1994 | A weight-size trade-off for circuits with MOD m gates. | Vince Grolmusz |
| 1994 | Lower bounds on testing membership to a polyhedron by algebraic decision trees. | Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1994 | Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. | Oded Goldreich, Avi Wigderson |
| 1994 | Computational complexity and knowledge complexity (extended abstract). | Oded Goldreich, Rafail Ostrovsky, Erez Petrank |
| 1994 | .879-approximation algorithms for MAX CUT and MAX 2SAT. | Michel X. Goemans, David P. Williamson |
| 1994 | An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. | Naveen Garg, Dorit S. Hochbaum |
| 1994 | Efficient splitting off algorithms for graphs. | Harold N. Gabow |
| 1994 | Optimality and domination in repeated games with bounded players. | Lance Fortnow, Duke Whang |
| 1994 | A minimal model for secure computation (extended abstract). | Uriel Feige, Joe Kilian, Moni Naor |
| 1994 | Two prover protocols: low error at affordable rates. | Uriel Feige, Joe Kilian |
| 1994 | The connectivity carcass of a vertex subset in a graph and its incremental maintenance. | Yefim Dinitz, Alek Vainshtein |
| 1994 | On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). | Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson |
| 1994 | Polylog-time and near-linear work approximation scheme for undirected shortest paths. | Edith Cohen |
| 1994 | A near optimal algorithm for edge separators (preliminary version). | Fan R. K. Chung, Shing-Tung Yau |
| 1994 | Computational geometry: a retrospective. | Bernard Chazelle |
| 1994 | Improved algorithms via approximations of probability distributions (extended abstract). | Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan |
| 1994 | Scalable expanders: exploiting hierarchical random wiring. | Eric A. Brewer, Frederic T. Chong, Tom Leighton |
| 1994 | Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. | Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett |
| 1994 | Weakly learning DNF and characterizing statistical query learning using Fourier analysis. | Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich |
| 1994 | The minimum latency problem. | Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan |