| 1994 | "Go With the Winners" Algorithms David J. Aldous, Umesh V. Vazirani |
| 1994 | (De)randomized Construction of Small Sample Spaces in \calNC David R. Karger, Daphne Koller |
| 1994 | 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994 |
| 1994 | A Lower Bound for the Monotone Depth of Connectivity Andrew Chi-Chih Yao |
| 1994 | A New Efficient Radix Sort Arne Andersson, Stefan Nilsson |
| 1994 | A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes Yoram Hirshfeld, Mark Jerrum, Faron Moller |
| 1994 | A Spectral Approach to Lower Bounds Bernard Chazelle |
| 1994 | A Theory of Competitive Analysis for Distributed Algorithms Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
| 1994 | A note on the Theta number of Lovász and the generalized Delsarte bound Mario Szegedy |
| 1994 | Algebraic Computation Trees in Characteristi p>0 (Extended Abstract) Michael Ben-Or |
| 1994 | Algorithmic Number Theory-The Complexity Contribution Leonard M. Adleman |
| 1994 | Algorithms for Quantum Computation: Discrete Logarithms and Factoring Peter W. Shor |
| 1994 | An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution Jeffrey C. Jackson |
| 1994 | An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem C. Andrew Neff, John H. Reif |
| 1994 | Approximate Graph Coloring by Semidefinite Programming David R. Karger, Rajeev Motwani, Madhu Sudan |
| 1994 | Beyond Competitive Analysis Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | CS Proofs (Extended Abstracts) Silvio Micali |
| 1994 | Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates Dima Grigoriev, Nicolai N. Vorobjov Jr. |
| 1994 | Computing with Very Weak Random Sources Aravind Srinivasan, David Zuckerman |
| 1994 | Efficient Average-Case Algorithms for the Modular Group Jin-Yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu |
| 1994 | Efficient Oblivious Branching Programs for Threshold Functions Rakesh K. Sinha, Jayram S. Thathachar |
| 1994 | Estimating the Size of the Transitive Closure in Linear Time Edith Cohen |
| 1994 | Expander Codes Michael Sipser, Daniel A. Spielman |
| 1994 | Fast and Feasible Periodic Sorting Networks of Constant Depth Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff, Rolf Wanka |
| 1994 | Fast and Lean Self-Stabilizing Asynchronous Protocols Gene Itkis, Leonid A. Levin |
| 1994 | Finding separator cuts in planar graphs within twice the optimal Naveen Garg, Huzur Saran, Vijay V. Vazirani |
| 1994 | Finding the k Shortest Paths David Eppstein |
| 1994 | Fully Dynamic Cycle-Equivalence in Graphs Monika Rauch Henzinger |
| 1994 | Graph Connectivity and Monadic NP Thomas Schwentick |
| 1994 | IP over connection-oriented networks and distributional paging Carsten Lund, Steven J. Phillips, Nick Reingold |
| 1994 | Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation Baruch Awerbuch, Yossi Azar |
| 1994 | Long Tours and Short Superstrings (Preliminary Version) S. Rao Kosaraju, James K. Park, Clifford Stein |
| 1994 | Lower Bound on Hilbert's Nullstellensatz and propositional proofs Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák |
| 1994 | Markov Chains and Polynomial Time Algorithms Ravi Kannan |
| 1994 | Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time Karsten Weihe |
| 1994 | Maximum Agreement Subtree in a Set of Evolutionary Trees-Metrics and Efficient Algorithms Dmitry Keselman, Amihood Amir |
| 1994 | Measure on Small Complexity Classes, with Applications for BPP Eric Allender, Martin Strauss |
| 1994 | More Output-Sensitive Geometric Algorithms (Extended Abstract) Kenneth L. Clarkson |
| 1994 | Motion Planning on a Graph (Extended Abstract) Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki |
| 1994 | Multi-Index Hashing for Information Retrieval Daniel H. Greene, Michal Parnas, F. Frances Yao |
| 1994 | Nearly Tight Bounds for Wormhole Routing Abhiram G. Ranade, Saul Schleimer, Daniel Shawcross Wilkerson |
| 1994 | On Learning Discretized Geometric Concepts (Extended Abstract) Nader H. Bshouty, Zhixiang Chen, Steven Homer |
| 1994 | On Monotone Formula Closure of SZK Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung |
| 1994 | On Rank vs. Communication Complexity Noam Nisan, Avi Wigderson |
| 1994 | On Syntactic versus Computational Views of Approximability Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani |
| 1994 | On the Combinatorial and Algebraic Complexity of Quantifier Elimination Saugata Basu, Richard Pollack, Marie-Françoise Roy |
| 1994 | On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-in (Extended Abstract) György Turán, Farrokh Vatan |
| 1994 | On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma |
| 1994 | On the Power of Quantum Computation Daniel R. Simon |
| 1994 | On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs Joe Kilian |
| 1994 | On the robustness of functional equations Ronitt Rubinfeld |
| 1994 | On-line Admission Control and Circuit Routing for High Performance Computing and Communication Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani |
| 1994 | Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract) Martin Farach, Mikkel Thorup |
| 1994 | Optimizing Static Calendar Queues K. Bruce Erickson, Richard E. Ladner, Anthony LaMarca |
| 1994 | PAC Learning with Irrelevant Attributes Aditi Dhagat, Lisa Hellerstein |
| 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 | Priority Encoding Transmission Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan |
| 1994 | Products and Help Bits in Decision Trees Noam Nisan, Steven Rudich, Michael E. Saks |
| 1994 | Program Result-Checking: A Theory of Testing Meets a Test of Theory Manuel Blum, Hal Wasserman |
| 1994 | Randomized Simplex Algorithms on Klee-Mintny Cubes Bernd Gärtner, Günter M. Ziegler |
| 1994 | Randomized and deterministic algorithms for geometric spanners of small diameter Sunil Arya, David M. Mount, Michiel H. M. Smid |
| 1994 | Randomness-Efficient Oblivious Sampling Mihir Bellare, John Rompel |
| 1994 | Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract) R. Ravi |
| 1994 | Reducibility and Completeness in Multi-Party Private Computations Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky |
| 1994 | Scheduling Multithreaded Computations by Work Stealing Robert D. Blumofe |
| 1994 | Set constraints with projections are in NEXPTIME Witold Charatonik, Leszek Pacholski |
| 1994 | Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture Anil Kamath, Rajeev Motwani, Krishna V. Palem, Paul G. Spirakis |
| 1994 | The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein |
| 1994 | The Load, Capacity and Availability of Quorum Systems Moni Naor, Avishai Wool |
| 1994 | The Localization Problem for Mobile Robots Jon M. Kleinberg |
| 1994 | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs Michael A. Bender, Donna K. Slonim |
| 1994 | The geometry of graphs and some of its algorithmic applications Nathan Linial, Eran London, Yuri Rabinovich |
| 1994 | Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping Haim Kaplan, Ron Shamir, Robert Endre Tarjan |