| 1994 | Optimizing Static Calendar Queues | K. Bruce Erickson, Richard E. Ladner, Anthony LaMarca |
| 1994 | Finding the k Shortest Paths | David Eppstein |
| 1994 | PAC Learning with Irrelevant Attributes | Aditi Dhagat, Lisa Hellerstein |
| 1994 | Estimating the Size of the Transitive Closure in Linear Time | Edith Cohen |
| 1994 | More Output-Sensitive Geometric Algorithms (Extended Abstract) | Kenneth L. Clarkson |
| 1994 | A Spectral Approach to Lower Bounds | Bernard Chazelle |
| 1994 | Set constraints with projections are in NEXPTIME | Witold Charatonik, Leszek Pacholski |
| 1994 | The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices | Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein |
| 1994 | Efficient Average-Case Algorithms for the Modular Group | Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu |
| 1994 | On Learning Discretized Geometric Concepts (Extended Abstract) | Nader H. Bshouty, Zhixiang Chen, Steven Homer |
| 1994 | Program Result-Checking: A Theory of Testing Meets a Test of Theory | Manuel Blum, Hal Wasserman |
| 1994 | Scheduling Multithreaded Computations by Work Stealing | Robert D. Blumofe |
| 1994 | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs | Michael A. Bender, Donna K. Slonim |
| 1994 | Algebraic Computation Trees in Characteristi p>0 (Extended Abstract) | Michael Ben-Or |
| 1994 | Randomness-Efficient Oblivious Sampling | Mihir Bellare, John Rompel |
| 1994 | Lower Bound on Hilbert's Nullstellensatz and propositional proofs | Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk |
| 1994 | On the Combinatorial and Algebraic Complexity of Quantifier Elimination | Saugata Basu, Richard Pollack, Marie-Franoise Roy |
| 1994 | On-line Admission Control and Circuit Routing for High Performance Computing and Communication | Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani |
| 1994 | Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation | Baruch Awerbuch, Yossi Azar |
| 1994 | Randomized and deterministic algorithms for geometric spanners of small diameter | Sunil Arya, David M. Mount, Michiel H. M. Smid |
| 1994 | A New Efficient Radix Sort | Arne Andersson, Stefan Nilsson |
| 1994 | Parallel Algorithms for Higher-Dimensional Convex Hulls | Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos |
| 1994 | Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs | Noga Alon, Alan M. Frieze, Dominic Welsh |
| 1994 | Measure on Small Complexity Classes, with Applications for BPP | Eric Allender, Martin Strauss |
| 1994 | "Go With the Winners" Algorithms | David J. Aldous, Umesh V. Vazirani |