| 1994 | .879-approximation algorithms for MAX CUT and MAX 2SAT. Michel X. Goemans, David P. Williamson |
| 1994 | A coding theorem for distributed computation. Sridhar Rajagopalan, Leonard J. Schulman |
| 1994 | A functional equation often arising in the analysis of algorithms (extended abstract). Philippe Jacquet, Wojciech Szpankowski |
| 1994 | A minimal model for secure computation (extended abstract). Uriel Feige, Joe Kilian, Moni Naor |
| 1994 | A near optimal algorithm for edge separators (preliminary version). Fan R. K. Chung, Shing-Tung Yau |
| 1994 | A randomized linear-time algorithm for finding minimum spanning trees. Philip N. Klein, Robert Endre Tarjan |
| 1994 | A simple constructive computability theorem for wait-free computation. Maurice Herlihy, Nir Shavit |
| 1994 | A spectral technique for coloring random 3-colorable graphs (preliminary version). Noga Alon, Nabil Kahalé |
| 1994 | A theory of clock synchronization (extended abstract). Boaz Patt-Shamir, Sergio Rajsbaum |
| 1994 | A weight-size trade-off for circuits with MOD m gates. Vince Grolmusz |
| 1994 | Aligning sequences via an evolutionary tree: complexity and approximation. Tao Jiang, Eugene L. Lawler, Lusheng Wang |
| 1994 | Alpha-algorithms for incremental planarity testing (preliminary version). Johannes A. La Poutré |
| 1994 | An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. Naveen Garg, Dorit S. Hochbaum |
| 1994 | An accelerated interior point method whose running time depends only on A (extended abstract). Stephen A. Vavasis, Yinyu Ye |
| 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 | Augmenting undirected connectivity in RNC and in randomized Õ( András A. Benczúr |
| 1994 | Balanced allocations (extended abstract). Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal |
| 1994 | Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett |
| 1994 | Choosing a learning team: a topological approach. Kalvis Apsitis, Rusins Freivalds, Carl H. Smith |
| 1994 | Circuit complexity: from the worst case to the average case. Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer |
| 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 | Computational complexity and knowledge complexity (extended abstract). Oded Goldreich, Rafail Ostrovsky, Erez Petrank |
| 1994 | Computational geometry: a retrospective. Bernard Chazelle |
| 1994 | Decision tree complexity and Betti numbers. Andrew Chi-Chih Yao |
| 1994 | Derandomization through approximation: an David R. Karger, Rajeev Motwani |
| 1994 | Efficient asynchronous distributed symmetry breaking. Baruch Awerbuch, Lenore Cowen, Mark A. Smith |
| 1994 | Efficient probabilistic checkable proofs and applications to approximation. Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell |
| 1994 | Efficient routing in all-optical networks. Prabhakar Raghavan, Eli Upfal |
| 1994 | Efficient splitting off algorithms for graphs. Harold N. Gabow |
| 1994 | Fast algorithms for finding randomized strategies in game trees. Daphne Koller, Nimrod Megiddo, Bernhard von Stengel |
| 1994 | Faster shortest-path algorithms for planar graphs. Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian |
| 1994 | Fault-tolerant scheduling. Bala Kalyanasundaram, Kirk Pruhs |
| 1994 | Greed is good: approximating independent sets in sparse and bounded-degree graphs. Magnús M. Halldórsson, Jaikumar Radhakrishnan |
| 1994 | How to share a function securely. Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung |
| 1994 | Improved algorithms via approximations of probability distributions (extended abstract). Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan |
| 1994 | Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. Baruch Awerbuch, Tom Leighton |
| 1994 | Improved data structures for fully dynamic biconnectivity. Monika Rauch |
| 1994 | Improved non-approximability results. Mihir Bellare, Madhu Sudan |
| 1994 | Low degree spanning trees of small weight. Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 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 | Lower bounds on testing membership to a polyhedron by algebraic decision trees. Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1994 | Natural proofs. Alexander A. Razborov, Steven Rudich |
| 1994 | Nearly-linear size holographic proofs. Alexander Polishchuk, Daniel A. Spielman |
| 1994 | Non-standard stringology: algorithms and complexity. S. Muthukrishnan, Krishna V. Palem |
| 1994 | On complexity as bounded rationality (extended abstract). Christos H. Papadimitriou, Mihalis Yannakakis |
| 1994 | On construction of Howard J. Karloff, Yishay Mansour |
| 1994 | On contention resolution protocols and associated probabilistic phenomena. Philip D. MacKenzie, C. Greg Plaxton, Rajmohan Rajaraman |
| 1994 | On lazy randomized incremental construction. Mark de Berg, Katrin Dobrindt, Otfried Schwarzkopf |
| 1994 | On point location and motion planning among simplices. Marco Pellegrini |
| 1994 | On the Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | On the complexity of negation-limited Boolean networks. Keisuke Tanaka, Tetsuro Nishino |
| 1994 | On the computational power of depth 2 circuits with threshold and modulo gates. Matthias Krause, Pavel Pudlák |
| 1994 | On the fault tolerance of the butterfly. Anna R. Karlin, Greg Nelson, Hisao Tamaki |
| 1994 | On the learnability of discrete distributions. Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie |
| 1994 | On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson |
| 1994 | Optimal parallel string algorithms: sorting, merging and computing the minimum. Torben Hagerup |
| 1994 | Optimal parallel suffix tree construction. Ramesh Hariharan |
| 1994 | Optimality and domination in repeated games with bounded players. Lance Fortnow, Duke Whang |
| 1994 | Polylog-time and near-linear work approximation scheme for undirected shortest paths. Edith Cohen |
| 1994 | Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada Frank Thomson Leighton, Michael T. Goodrich |
| 1994 | Pseudorandom generators and learning algorithms for AC. Meera Sitharam |
| 1994 | Pseudorandomness for network algorithms. Russell Impagliazzo, Noam Nisan, Avi Wigderson |
| 1994 | Random sampling in cut, flow, and network design problems. David R. Karger |
| 1994 | Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version). S. Rao Kosaraju |
| 1994 | Receipt-free secret-ballot elections (extended abstract). Josh Cohen Benaloh, Dwight Tuinstra |
| 1994 | Scalable expanders: exploiting hierarchical random wiring. Eric A. Brewer, Frederic T. Chong, Tom Leighton |
| 1994 | Search for the maximum of a random walk. Andrew M. Odlyzko |
| 1994 | Simple and efficient leader election in the full information model. Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani |
| 1994 | Simple strategies for large zero-sum games with applications to complexity theory. Richard J. Lipton, Neal E. Young |
| 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 | Symmetry breaking for suffix tree construction. Süleyman Cenk Sahinalp, Uzi Vishkin |
| 1994 | The amazing power of pairwise independence (abstract). Avi Wigderson |
| 1994 | The complexity of searching a sorted array of strings. Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson |
| 1994 | The complexity of verification. Robert P. Kurshan |
| 1994 | The computational complexity of recognizing permutation functions. Keju Ma, Joachim von zur Gathen |
| 1994 | The connectivity carcass of a vertex subset in a graph and its incremental maintenance. Yefim Dinitz, Alek Vainshtein |
| 1994 | The independence of the modulo Miklós Ajtai |
| 1994 | The minimum latency problem. Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan |
| 1994 | Time bounds for mutual exclusion and related problems. Jae-Heon Yang, James H. Anderson |
| 1994 | Time-adaptive algorithms for synchronization. Rajeev Alur, Hagit Attiya, Gadi Taubenfeld |
| 1994 | Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. Oded Goldreich, Avi Wigderson |
| 1994 | Trade-offs between communication throughput and parallel time. Yishay Mansour, Noam Nisan, Uzi Vishkin |
| 1994 | Two heads are better than two tapes. Tao Jiang, Joel I. Seiferas, Paul M. B. Vitányi |
| 1994 | Two prover protocols: low error at affordable rates. Uriel Feige, Joe Kilian |
| 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 |