| 1996 | Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. | Alok Aggarwal, Jon M. Kleinberg, David P. Williamson |
| 1996 | Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract). | Yehuda Afek, Yishay Mansour, Zvi Ostfeld |
| 1995 | Security of quantum protocols against coherent measurements. | Andrew Chi-Chih Yao |
| 1995 | Average-case completeness of a word problem for groups. | Jie Wang |
| 1995 | Improved approximations of packing and covering problems. | Aravind Srinivasan |
| 1995 | Linear-time encodable and decodable error-correcting codes. | Daniel A. Spielman |
| 1995 | Explicit dispersers with polylog degree. | Michael E. Saks, Aravind Srinivasan, Shiyu Zhou |
| 1995 | Work efficient parallel solution of Toeplitz systems and polynomial GCD. | John H. Reif |
| 1995 | A parallel repetition theorem. | Ran Raz |
| 1995 | Recognition of graphs with threshold dimension two. | Thomas Raschle, Klaus Simon |
| 1995 | Stochastic contention resolution with short delays. | Prabhakar Raghavan, Eli Upfal |
| 1995 | A computational view of population genetics. | Yuval Rabani, Yuri Rabinovich, Alistair Sinclair |
| 1995 | Two Steiner tree packing problems (Extended Abstract). | William R. Pulleyblank |
| 1995 | A lower bound for integer multiplication with read-once branching programs. | Stephen Ponzio |
| 1995 | Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. | Victor Y. Pan |
| 1995 | On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. | Noam Nisan, Avi Wigderson |
| 1995 | Symmetric logspace is closed under complement. | Noam Nisan, Amnon Ta-Shma |
| 1995 | On data structures and asymmetric communication complexity. | Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson |
| 1995 | A Delaunay based numerical method for three dimensions: generation, formulation, and partition. | Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington |
| 1995 | Many-to-one packet routing on grids (Extended Abstract). | Yishay Mansour, Boaz Patt-Shamir |
| 1995 | Efficient stopping rules for Markov chains. | Lszl Lovsz, Peter Winkler |
| 1995 | Log-space polynomial end-to-end communication. | Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosn |
| 1995 | On randomized one-round communication complexity. | Ilan Kremer, Noam Nisan, Dana Ron |
| 1995 | Large-scale assembly of DNA strings and space-efficient construction of suffix trees. | S. Rao Kosaraju, Arthur L. Delcher |
| 1995 | Approximations for the disjoint paths problem in high-diameter planar networks. | Jon M. Kleinberg, va Tardos |