| 1996 | Verifying Identities (extended abstract). | Sridhar Rajagopalan, Leonard J. Schulman |
| 1996 | Computationally Hard Algebraic Problems (extended abstract). | Michael O. Rabin |
| 1996 | Path Coloring on the Mesh. | Yuval Rabani |
| 1996 | Fast Fault-Tolerant Concurrent Access to Shared Objects. | C. Greg Plaxton, Rajmohan Rajaraman |
| 1996 | On the Knowledge Complexity of NP. | Erez Petrank, Gbor Tardos |
| 1996 | Load Balancing and Density Dependent Jump Markov Processes (extended abstract). | Michael Mitzenmacher |
| 1996 | Factoring Graphs to Bound Mixing Rates. | Neal Madras, Dana Randall |
| 1996 | Efficient Self-Testing/Self-Correction of Linear Recurrences. | Ravi Kumar, D. Sivakumar |
| 1996 | Computing Permanents over Fields of Characteristic 3: Where and Why It Becomes Difficult (extended abstract). | Grigory Kogan |
| 1996 | Short Paths in Expander Graphs. | Jon M. Kleinberg, Ronitt Rubinfeld |
| 1996 | Single-Source Unsplittable Flow. | Jon M. Kleinberg |
| 1996 | Near-Optimal Parallel Prefetching and Caching. | Tracy Kimbrel, Anna R. Karlin |
| 1996 | Approximate Strip Packing. | Claire Kenyon, Eric Rmila |
| 1996 | Sampling According to the Multivariate Normal Density. | Ravi Kannan, Guangxing Li |
| 1996 | Solving Systems of Polynomial Congruences Modulo a Large Prime (extended abstract). | Ming-Deh A. Huang, Yiu-Chung Wong |
| 1996 | Computing Vertex Connectivity: New Bounds from Old Techniques. | Monika Rauch Henzinger, Satish Rao, Harold N. Gabow |
| 1996 | Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols. | Friedhelm Meyer auf der Heide, Christian Scheideler |
| 1996 | Clique is Hard to Approximate Within n | Johan Hstad |
| 1996 | Equivalence in Finite-Variable Logics is Complete for Polynomial Time. | Martin Grohe |
| 1996 | Property Testing and Its Connection to Learning and Approximation. | Oded Goldreich, Shafi Goldwasser, Dana Ron |
| 1996 | A 3-Approximation for the Minimum Tree Spanning k Vertices. | Naveen Garg |
| 1996 | The Regularity Lemma and Approximation Schemes for Dense Problems. | Alan M. Frieze, Ravi Kannan |
| 1996 | Learning Linear Transformations. | Alan M. Frieze, Mark Jerrum, Ravi Kannan |
| 1996 | An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. | Guy Even, Joseph Naor, Leonid Zosin |
| 1996 | Efficient Information Gathering on the Internet (extended abstract). | Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, Orli Waarts |