| 1996 | Noise-Tolerant Learning Near the Information-Theoretic Bound. | Nicol Cesa-Bianchi, Eli Dichterman, Paul Fischer, Hans Ulrich Simon |
| 1996 | Adaptively Secure Multi-Party Computation. | Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor |
| 1996 | Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. | Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki |
| 1996 | Towards the Learnability of DNF Formulae. | Nader H. Bshouty |
| 1996 | Dynamic Deflection Routing on Arrays (Preliminary Version). | Andrei Z. Broder, Eli Upfal |
| 1996 | Adversarial Queueing Theory. | Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson |
| 1996 | Constructing Evolutionary Trees in the Presence of Polymorphic Characters. | Maria Luisa Bonet, Cynthia A. Phillips, Tandy J. Warnow, Shibu Yooseph |
| 1996 | A Constant-factor Approximation Algorithm for the | Avrim Blum, R. Ravi, Santosh S. Vempala |
| 1996 | Pushing Disks Together - The Continuous-Motion Case. | Marshall W. Bern, Amit Sahai |
| 1996 | Reconstructing a Three-Dimensional Model with Arbitrary Errors. | Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton |
| 1996 | Learning Sat- | Francesco Bergadano, Dario Catalano, Stefano Varricchio |
| 1996 | Approximating | Andrs A. Benczr, David R. Karger |
| 1996 | Adaptive Zero Knowledge and Computational Equivocation (Extended Abstract). | Donald Beaver |
| 1996 | Correlated Pseudorandomness and the Complexity of Private Computations. | Donald Beaver |
| 1996 | Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract). | Saugata Basu, Richard Pollack, Marie-Franoise Roy |
| 1996 | On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets. | Saugata Basu |
| 1996 | Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. | Yair Bartal, Amos Fiat, Stefano Leonardi |
| 1996 | Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. | Lszl Babai, Anna Gl, Jnos Kollr, Lajos Rnyai, Tibor Szab, Avi Wigderson |
| 1996 | Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract). | Baruch Awerbuch, Yossi Azar, Amos Fiat, Frank Thomson Leighton |
| 1996 | Modular Competitiveness for Distributed Algorithms. | James Aspnes, Orli Waarts |
| 1996 | Robot Navigation with Range Queries. | Dana Angluin, Jeffery R. Westbrook, Wenhong Zhu |
| 1996 | Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). | Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang |
| 1996 | The Space Complexity of Approximating the Frequency Moments. | Noga Alon, Yossi Matias, Mario Szegedy |
| 1996 | The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract). | Eric Allender, Robert Beals, Mitsunori Ogihara |
| 1996 | Generating Hard Instances of Lattice Problems (Extended Abstract). | Mikls Ajtai |