| 1995 | Distinguishing tests for nondeterministic and probabilistic machines. | Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis |
| 1995 | Knowledge on the average-perfect, statistical and logarithmic. | William Aiello, Mihir Bellare, Ramarathnam Venkatesan |
| 1995 | Motion planning for a steering-constrained robot through moderate obstacles. | Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki |
| 1995 | Wait-free made fast (Extended Abstract). | Yehuda Afek, Dalia Dauber, Dan Touitou |
| 1995 | Parallel randomized load balancing (Preliminary Version). | Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Eilstrup Rasmussen |
| 1994 | Decision tree complexity and Betti numbers. | Andrew Chi-Chih Yao |
| 1994 | Time bounds for mutual exclusion and related problems. | Jae-Heon Yang, James H. Anderson |
| 1994 | The amazing power of pairwise independence (abstract). | Avi Wigderson |
| 1994 | An accelerated interior point method whose running time depends only on A (extended abstract). | Stephen A. Vavasis, Yinyu Ye |
| 1994 | On the complexity of negation-limited Boolean networks. | Keisuke Tanaka, Tetsuro Nishino |
| 1994 | Pseudorandom generators and learning algorithms for AC. | Meera Sitharam |
| 1994 | How to share a function securely. | Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung |
| 1994 | Symmetry breaking for suffix tree construction. | Sleyman Cenk Sahinalp, Uzi Vishkin |
| 1994 | Natural proofs. | Alexander A. Razborov, Steven Rudich |
| 1994 | Improved data structures for fully dynamic biconnectivity. | Monika Rauch |
| 1994 | A coding theorem for distributed computation. | Sridhar Rajagopalan, Leonard J. Schulman |
| 1994 | Efficient routing in all-optical networks. | Prabhakar Raghavan, Eli Upfal |
| 1994 | Alpha-algorithms for incremental planarity testing (preliminary version). | Johannes A. La Poutr |
| 1994 | Nearly-linear size holographic proofs. | Alexander Polishchuk, Daniel A. Spielman |
| 1994 | On point location and motion planning among simplices. | Marco Pellegrini |
| 1994 | A theory of clock synchronization (extended abstract). | Boaz Patt-Shamir, Sergio Rajsbaum |
| 1994 | On complexity as bounded rationality (extended abstract). | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1994 | Simple and efficient leader election in the full information model. | Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani |
| 1994 | Search for the maximum of a random walk. | Andrew M. Odlyzko |
| 1994 | Non-standard stringology: algorithms and complexity. | S. Muthukrishnan, Krishna V. Palem |