| 1994 | On lazy randomized incremental construction. | Mark de Berg, Katrin Dobrindt, Otfried Schwarzkopf |
| 1994 | Augmenting undirected connectivity in RNC and in randomized ( | Andrs A. Benczr |
| 1994 | Receipt-free secret-ballot elections (extended abstract). | Josh Cohen Benaloh, Dwight Tuinstra |
| 1994 | Improved non-approximability results. | Mihir Bellare, Madhu Sudan |
| 1994 | Efficient probabilistic checkable proofs and applications to approximation. | Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell |
| 1994 | Balanced allocations (extended abstract). | Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal |
| 1994 | Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. | Baruch Awerbuch, Tom Leighton |
| 1994 | Efficient asynchronous distributed symmetry breaking. | Baruch Awerbuch, Lenore Cowen, Mark A. Smith |
| 1994 | Simulating access to hidden information while learning. | Peter Auer, Philip M. Long |
| 1994 | Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). | Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani |
| 1994 | Choosing a learning team: a topological approach. | Kalvis Apsitis, Rusins Freivalds, Carl H. Smith |
| 1994 | The complexity of searching a sorted array of strings. | Arne Andersson, Torben Hagerup, Johan Hstad, Ola Petersson |
| 1994 | Time-adaptive algorithms for synchronization. | Rajeev Alur, Hagit Attiya, Gadi Taubenfeld |
| 1994 | Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. | Noga Alon, Raphael Yuster, Uri Zwick |
| 1994 | A spectral technique for coloring random 3-colorable graphs (preliminary version). | Noga Alon, Nabil Kahal |
| 1994 | The independence of the modulo | Mikls Ajtai |
| 1993 | A primal-dual approximation algorithm for generalized Steiner network problems. | David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani |
| 1993 | Expanders that beat the eigenvalue bound: explicit construction and applications. | Avi Wigderson, David Zuckerman |
| 1993 | Locality based graph coloring. | Mario Szegedy, Sundar Vishwanathan |
| 1993 | On the generation of multivariate polynomials which are hard to factor. | Adi Shamir |
| 1993 | Deterministic coding for interactive communication. | Leonard J. Schulman |
| 1993 | Wait-free k-set agreement is impossible: the topology of public knowledge. | Michael E. Saks, Fotios Zaharoglou |
| 1993 | Many birds with one stone: multi-objective approximation algorithms. | R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III |
| 1993 | Cryptographic defense against traffic analysis. | Charles Rackoff, Daniel R. Simon |
| 1993 | Modified ranks of tensors and the size of circuits. | Pavel Pudlk, Vojtech Rdl |