| 1994 | IP over connection-oriented networks and distributional paging | Carsten Lund, Steven J. Phillips, Nick Reingold |
| 1994 | The geometry of graphs and some of its algorithmic applications | Nathan Linial, Eran London, Yuri Rabinovich |
| 1994 | Fast and Feasible Periodic Sorting Networks of Constant Depth | Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff, Rolf Wanka |
| 1994 | Reducibility and Completeness in Multi-Party Private Computations | Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky |
| 1994 | Beyond Competitive Analysis | Elias Koutsoupias, Christos H. Papadimitriou |
| 1994 | Long Tours and Short Superstrings (Preliminary Version) | S. Rao Kosaraju, James K. Park, Clifford Stein |
| 1994 | On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates | Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma |
| 1994 | The Localization Problem for Mobile Robots | Jon M. Kleinberg |
| 1994 | On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs | Joe Kilian |
| 1994 | On Syntactic versus Computational Views of Approximability | Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani |
| 1994 | Maximum Agreement Subtree in a Set of Evolutionary Trees-Metrics and Efficient Algorithms | Dmitry Keselman, Amihood Amir |
| 1994 | Approximate Graph Coloring by Semidefinite Programming | David R. Karger, Rajeev Motwani, Madhu Sudan |
| 1994 | (De)randomized Construction of Small Sample Spaces in \calNC | David R. Karger, Daphne Koller |
| 1994 | Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping | Haim Kaplan, Ron Shamir, Robert Endre Tarjan |
| 1994 | Markov Chains and Polynomial Time Algorithms | Ravi Kannan |
| 1994 | Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture | Anil Kamath, Rajeev Motwani, Krishna V. Palem, Paul G. Spirakis |
| 1994 | An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution | Jeffrey C. Jackson |
| 1994 | Fast and Lean Self-Stabilizing Asynchronous Protocols | Gene Itkis, Leonid A. Levin |
| 1994 | A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes | Yoram Hirshfeld, Mark Jerrum, Faron Moller |
| 1994 | Fully Dynamic Cycle-Equivalence in Graphs | Monika Rauch Henzinger |
| 1994 | Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates | Dima Grigoriev, Nicolai N. Vorobjov Jr. |
| 1994 | Multi-Index Hashing for Information Retrieval | Daniel H. Greene, Michal Parnas, F. Frances Yao |
| 1994 | Randomized Simplex Algorithms on Klee-Mintny Cubes | Bernd Grtner, Gnter M. Ziegler |
| 1994 | Finding separator cuts in planar graphs within twice the optimal | Naveen Garg, Huzur Saran, Vijay V. Vazirani |
| 1994 | Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract) | Martin Farach, Mikkel Thorup |