| 1996 | Better Lower Bounds for Halfspace Emptiness. | Jeff Erickson |
| 1996 | Approximate Checking of Polynomials and Functional Equations (extended abstract). | Funda Ergn, Ravi Kumar, Ronitt Rubinfeld |
| 1996 | A Decision Procedure for Unitary Linear Quantum Cellular Automata. | Christoph Drr, Miklos Santha |
| 1996 | Median Selection Requires (2+epsilon)n Comparisons. | Dorit Dor, Uri Zwick |
| 1996 | All Pairs Almost Shortest Paths. | Dorit Dor, Shay Halperin, Uri Zwick |
| 1996 | The Optimal Path-Matching Problem. | William H. Cunningham, James F. Geelen |
| 1996 | Universal Data Compression and Portfolio Selection. | Thomas M. Cover |
| 1996 | Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). | Joseph Cheriyan, Ramakrishna Thurimella |
| 1996 | Approximate Option Pricing. | Prasad Chalasani, Somesh Jha, Isaac Saias |
| 1996 | Incoercible Multiparty Computation (extended abstract). | Ran Canetti, Rosario Gennaro |
| 1996 | A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract). | Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1996 | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. | Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1996 | Pseudorandom Functions Revisited: The Cascade Construction and Its Concrete Security. | Mihir Bellare, Ran Canetti, Hugo Krawczyk |
| 1996 | On the Applications of Multiplicity Automata in Learning. | Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio |
| 1996 | Simplified and Improved Resolution Lower Bounds. | Paul Beame, Toniann Pitassi |
| 1996 | Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. | Yair Bartal |
| 1996 | Fault Tolerant Data Structures. | Yonatan Aumann, Michael A. Bender |
| 1996 | A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. | Sanjeev Arora, Alan M. Frieze, Haim Kaplan |
| 1996 | Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. | Sanjeev Arora |
| 1996 | Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. | Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou |
| 1996 | Optimal Dynamic Interval Management in External Memory (extended abstract). | Lars Arge, Jeffrey Scott Vitter |
| 1996 | New Algorithms for the Disk Scheduling Problem. | Matthew Andrews, Michael A. Bender, Lisa Zhang |
| 1996 | Universal Stability Results for Greedy Contention-Resolution Protocols. | Matthew Andrews, Baruch Awerbuch, Antonio Fernndez, Jon M. Kleinberg, Frank Thomson Leighton, Zhiyong Liu |
| 1996 | Static Dictionaries on AC | Arne Andersson, Peter Bro Miltersen, Sren Riis, Mikkel Thorup |
| 1996 | Faster Deterministic Sorting and Searching in Linear Space. | Arne Andersson |