| 1996 | Tree Data Structures for N-Body Simulation. | Richard J. Anderson |
| 1996 | Potential of the Approximation Method (extended abstract). | Kazuyuki Amano, Akira Maruoka |
| 1996 | The Geometry of Coin-Weighing Problems. | Noga Alon, Dmitry N. Kozlov, Van H. Vu |
| 1996 | Polynomial Simulations of Decohered Quantum Computers. | Dorit Aharonov, Michael Ben-Or |
| 1996 | The Boolean Isomorphism Problem. | Manindra Agrawal, Thomas Thierauf |
| 1996 | Binary Search Partitions for Fat Rectangles. | Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter |
| 1996 | New Coding Techniques for Improved Bandwidth Utilization. | Micah Adler |
| 1995 | A Scheduling Model for Reduced CPU Energy. | F. Frances Yao, Alan J. Demers, Scott Shenker |
| 1995 | Perspectives on Database Theory. | Mihalis Yannakakis |
| 1995 | On One-Dimensional Quantum Cellular Automata. | John Watrous |
| 1995 | Cognitive Computation (Extended Abstract). | Leslie G. Valiant |
| 1995 | A Unified Analysis of Paging and Caching. | Eric Torng |
| 1995 | Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time. | C. R. Subramanian |
| 1995 | Faster Approximate Agreement with Multi-Writer Registers. | Eric Schenk |
| 1995 | RSPACE(S) \subseteq DSPACE(S | Michael E. Saks, Shiyu Zhou |
| 1995 | Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems. | John H. Reif |
| 1995 | Pseudorandom Generators, Measure Theory, and Natural Proofs. | Kenneth W. Regan, D. Sivakumar, Jin-yi Cai |
| 1995 | Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines. | C. Greg Plaxton |
| 1995 | Contention Resolution with Bounded Delay. | Mike Paterson, Aravind Srinivasan |
| 1995 | Coding for Computing. | Alon Orlitsky, James R. Roche |
| 1995 | Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking. | Chris Okasaki |
| 1995 | Sparse P-Hard Sets Yield Space-Efficient Algorithms. | Mitsunori Ogihara |
| 1995 | Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). | Noam Nisan, Avi Wigderson |
| 1995 | Splitters and Near-Optimal Derandomization. | Moni Naor, Leonard J. Schulman, Aravind Srinivasan |
| 1995 | Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions. | Moni Naor, Omer Reingold |