| 1996 | 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14-16 October, 1996 |
| 1996 | A 3-Approximation for the Minimum Tree Spanning k Vertices. Naveen Garg |
| 1996 | A Decision Procedure for Unitary Linear Quantum Cellular Automata. Christoph Dürr, Miklos Santha |
| 1996 | A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract). Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1996 | A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. Sanjeev Arora, Alan M. Frieze, Haim Kaplan |
| 1996 | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1996 | All Pairs Almost Shortest Paths. Dorit Dor, Shay Halperin, Uri Zwick |
| 1996 | An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. Guy Even, Joseph Naor, Leonid Zosin |
| 1996 | An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups. Vijay V. Vazirani, Huzur Saran, B. Sundar Rajan |
| 1996 | Approximate Checking of Polynomials and Functional Equations (extended abstract). Funda Ergün, Ravi Kumar, Ronitt Rubinfeld |
| 1996 | Approximate Option Pricing. Prasad Chalasani, Somesh Jha, Isaac Saias |
| 1996 | Approximate Strip Packing. Claire Kenyon, Eric Rémila |
| 1996 | Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). Joseph Cheriyan, Ramakrishna Thurimella |
| 1996 | Better Lower Bounds for Halfspace Emptiness. Jeff Erickson |
| 1996 | Binary Search Partitions for Fat Rectangles. Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter |
| 1996 | Clique is Hard to Approximate Within n Johan Håstad |
| 1996 | Computationally Hard Algebraic Problems (extended abstract). Michael O. Rabin |
| 1996 | Computing Permanents over Fields of Characteristic 3: Where and Why It Becomes Difficult (extended abstract). Grigory Kogan |
| 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 | Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou |
| 1996 | Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (extended abstract). Süleyman Cenk Sahinalp, Uzi Vishkin |
| 1996 | Efficient Information Gathering on the Internet (extended abstract). Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, Orli Waarts |
| 1996 | Efficient Self-Testing/Self-Correction of Linear Recurrences. Ravi Kumar, D. Sivakumar |
| 1996 | Equivalence in Finite-Variable Logics is Complete for Polynomial Time. Martin Grohe |
| 1996 | Factoring Graphs to Bound Mixing Rates. Neal Madras, Dana Randall |
| 1996 | Fast Fault-Tolerant Concurrent Access to Shared Objects. C. Greg Plaxton, Rajmohan Rajaraman |
| 1996 | Faster Deterministic Sorting and Searching in Linear Space. Arne Andersson |
| 1996 | Fault Tolerant Data Structures. Yonatan Aumann, Michael A. Bender |
| 1996 | Fault-Tolerant Quantum Computation. Peter W. Shor |
| 1996 | Gadgets, Approximation, and Linear Programming (extended abstract). Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson |
| 1996 | Highly Fault-Tolerant Parallel Computation (extended abstract). Daniel A. Spielman |
| 1996 | Incoercible Multiparty Computation (extended abstract). Ran Canetti, Rosario Gennaro |
| 1996 | Learning Linear Transformations. Alan M. Frieze, Mark Jerrum, Ravi Kannan |
| 1996 | Load Balancing and Density Dependent Jump Markov Processes (extended abstract). Michael Mitzenmacher |
| 1996 | Maximum Likelihood Decoding of Reed Solomon Codes. Madhu Sudan |
| 1996 | Median Selection Requires (2+epsilon)n Comparisons. Dorit Dor, Uri Zwick |
| 1996 | Near-Optimal Parallel Prefetching and Caching. Tracy Kimbrel, Anna R. Karlin |
| 1996 | New Algorithms for the Disk Scheduling Problem. Matthew Andrews, Michael A. Bender, Lisa Zhang |
| 1996 | New Coding Techniques for Improved Bandwidth Utilization. Micah Adler |
| 1996 | On the Applications of Multiplicity Automata in Learning. Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio |
| 1996 | On the Knowledge Complexity of NP. Erez Petrank, Gábor Tardos |
| 1996 | Optimal Dynamic Interval Management in External Memory (extended abstract). Lars Arge, Jeffrey Scott Vitter |
| 1996 | Path Coloring on the Mesh. Yuval Rabani |
| 1996 | Polynomial Simulations of Decohered Quantum Computers. Dorit Aharonov, Michael Ben-Or |
| 1996 | Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. Sanjeev Arora |
| 1996 | Potential of the Approximation Method (extended abstract). Kazuyuki Amano, Akira Maruoka |
| 1996 | Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. Yair Bartal |
| 1996 | Property Testing and Its Connection to Learning and Approximation. Oded Goldreich, Shafi Goldwasser, Dana Ron |
| 1996 | Pseudorandom Functions Revisited: The Cascade Construction and Its Concrete Security. Mihir Bellare, Ran Canetti, Hugo Krawczyk |
| 1996 | Sampling According to the Multivariate Normal Density. Ravi Kannan, Guangxing Li |
| 1996 | Short Paths in Expander Graphs. Jon M. Kleinberg, Ronitt Rubinfeld |
| 1996 | Simplified and Improved Resolution Lower Bounds. Paul Beame, Toniann Pitassi |
| 1996 | Single-Source Unsplittable Flow. Jon M. Kleinberg |
| 1996 | Solving Systems of Polynomial Congruences Modulo a Large Prime (extended abstract). Ming-Deh A. Huang, Yiu-Chung Wong |
| 1996 | Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. Daniel A. Spielman, Shang-Hua Teng |
| 1996 | Static Dictionaries on AC Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup |
| 1996 | Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. Denis Thérien, Thomas Wilke |
| 1996 | The Boolean Isomorphism Problem. Manindra Agrawal, Thomas Thierauf |
| 1996 | The Geometry of Coin-Weighing Problems. Noga Alon, Dmitry N. Kozlov, Van H. Vu |
| 1996 | The Optimal Path-Matching Problem. William H. Cunningham, James F. Geelen |
| 1996 | The Regularity Lemma and Approximation Schemes for Dense Problems. Alan M. Frieze, Ravi Kannan |
| 1996 | Tree Data Structures for N-Body Simulation. Richard J. Anderson |
| 1996 | Universal Data Compression and Portfolio Selection. Thomas M. Cover |
| 1996 | Universal Stability Results for Greedy Contention-Resolution Protocols. Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon M. Kleinberg, Frank Thomson Leighton, Zhiyong Liu |
| 1996 | Verifying Identities (extended abstract). Sridhar Rajagopalan, Leonard J. Schulman |