| 1996 | A Constant-factor Approximation Algorithm for the Avrim Blum, R. Ravi, Santosh S. Vempala |
| 1996 | A Fast Quantum Mechanical Algorithm for Database Search. Lov K. Grover |
| 1996 | A Lower Bound for Randomized Algebraic Decision Trees. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky |
| 1996 | A Threshold of ln Uriel Feige |
| 1996 | A Tight Analysis of the Greedy Algorithm for Set Cover. Petr Slavík |
| 1996 | Adaptive Zero Knowledge and Computational Equivocation (Extended Abstract). Donald Beaver |
| 1996 | Adaptively Secure Multi-Party Computation. Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor |
| 1996 | Adversarial Queueing Theory. Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson |
| 1996 | Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space (Preliminary Version). Tamal K. Dey, Sumanta Guha |
| 1996 | An Yuan Ma |
| 1996 | Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger |
| 1996 | Approximating András A. Benczúr, David R. Karger |
| 1996 | Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang |
| 1996 | Characterizing Linear Size Circuits in Terms of Privacy. Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén |
| 1996 | Communication-Efficient Parallel Sorting (Preliminary Version). Michael T. Goodrich |
| 1996 | Computing Betti Numbers via Combinatorial Laplacians. Joel Friedman |
| 1996 | Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract). Saugata Basu, Richard Pollack, Marie-Françoise Roy |
| 1996 | Constructing Evolutionary Trees in the Presence of Polymorphic Characters. Maria Luisa Bonet, Cynthia A. Phillips, Tandy J. Warnow, Shibu Yooseph |
| 1996 | Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract). Yehuda Afek, Yishay Mansour, Zvi Ostfeld |
| 1996 | Correlated Pseudorandomness and the Complexity of Private Computations. Donald Beaver |
| 1996 | Deterministic Hiroshi Nagamochi, Toshihide Ibaraki |
| 1996 | Deterministic Restrictions in Circuit Complexity. Shiva Chaudhuri, Jaikumar Radhakrishnan |
| 1996 | Digital Signets: Self-Enforcing Protection of Digital Information (Preliminary Version). Cynthia Dwork, Jeffrey B. Lotspiech, Moni Naor |
| 1996 | Distributed Packet Switching in Arbitrary Networks. Yuval Rabani, Éva Tardos |
| 1996 | Dynamic Deflection Routing on Arrays (Preliminary Version). Andrei Z. Broder, Eli Upfal |
| 1996 | Efficient 3-D Range Searching in External Memory. Darren Erik Vengroff, Jeffrey Scott Vitter |
| 1996 | Efficient Algorithms for Inverting Evolution. Martin Farach, Sampath Kannan |
| 1996 | Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. Philip N. Klein, Hsueh-I Lu |
| 1996 | Efficiently Four-Coloring Planar Graphs. Neil Robertson, Daniel P. Sanders, Paul D. Seymour, Robin Thomas |
| 1996 | Embedding Graphs in an Arbitrary Surface in Linear Time. Bojan Mohar |
| 1996 | Evaluation May Be Easier Than Generation (Extended Abstract). Moni Naor |
| 1996 | Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson |
| 1996 | Fast Algorithms for Joseph Cheriyan, Ramakrishna Thurimella |
| 1996 | Fast Algorithms for Parametric Scheduling Come from Extensions to Parametric Maximum Flow. S. Thomas McCormick |
| 1996 | Faster Isomorphism Testing of Strongly Regular Graphs. Daniel A. Spielman |
| 1996 | Generating Hard Instances of Lattice Problems (Extended Abstract). Miklós Ajtai |
| 1996 | Generating Random Spanning Trees More Quickly than the Cover Time. David Bruce Wilson |
| 1996 | How Good is the Goemans-Williamson MAX CUT Algorithm? Howard J. Karloff |
| 1996 | Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees (Correction). S. Rao Kosaraju, Arthur L. Delcher |
| 1996 | Learning Sat- Francesco Bergadano, Dario Catalano, Stefano Varricchio |
| 1996 | Lower Bounds for Noisy Boolean Decision Trees. William S. Evans, Nicholas Pippenger |
| 1996 | Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. Yair Bartal, Amos Fiat, Stefano Leonardi |
| 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 | Minimum Cuts in Near-Linear Time. David R. Karger |
| 1996 | Modular Coloring Formulas Are Hard for Cutting Planes Proofs. Xudong Fu |
| 1996 | Modular Competitiveness for Distributed Algorithms. James Aspnes, Orli Waarts |
| 1996 | Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. Alok Aggarwal, Jon M. Kleinberg, David P. Williamson |
| 1996 | Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki |
| 1996 | Noise-Tolerant Learning Near the Information-Theoretic Bound. Nicolò Cesa-Bianchi, Eli Dichterman, Paul Fischer, Hans Ulrich Simon |
| 1996 | Non-Expansive Hashing. Nathan Linial, Ori Sasson |
| 1996 | Nondeterministic Communication with a Limited Number of Advice Bits. Juraj Hromkovic, Georg Schnitger |
| 1996 | On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets. Saugata Basu |
| 1996 | On Extracting Randomness From Weak Random Sources (Extended Abstract). Amnon Ta-Shma |
| 1996 | On Relationships between Statistical Zero-Knowledge Proofs. Tatsuaki Okamoto |
| 1996 | On the Boosting Ability of Top-Down Decision Tree Learning Algorithms. Michael J. Kearns, Yishay Mansour |
| 1996 | Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 Gary L. Miller |
| 1996 | Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). Ilan Newman, Mario Szegedy |
| 1996 | Purely Functional Representations of Catenable Sorted Lists. Haim Kaplan, Robert Endre Tarjan |
| 1996 | Pushing Disks Together - The Continuous-Motion Case. Marshall W. Bern, Amit Sahai |
| 1996 | Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. David Zuckerman |
| 1996 | Reconstructing a Three-Dimensional Model with Arbitrary Errors. Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton |
| 1996 | Robot Navigation with Range Queries. Dana Angluin, Jeffery R. Westbrook, Wenhong Zhu |
| 1996 | Sparsity Considerations in Dixon Resultants. Deepak Kapur, Tushar Saxena |
| 1996 | Testing of the Long Code and Hardness for Clique. Johan Håstad |
| 1996 | The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract). Eric Allender, Robert Beals, Mitsunori Ogihara |
| 1996 | The Linear-Array Conjecture in Communication Complexity is False. Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky |
| 1996 | The PL Hierarchy Collapses. Mitsunori Ogihara |
| 1996 | The Space Complexity of Approximating the Frequency Moments. Noga Alon, Yossi Matias, Mario Szegedy |
| 1996 | Towards a Syntactic Characterization of PTAS. Sanjeev Khanna, Rajeev Motwani |
| 1996 | Towards an Analysis of Local Optimization Algorithms. Tassos Dimitriou, Russell Impagliazzo |
| 1996 | Towards the Learnability of DNF Formulae. Nader H. Bshouty |
| 1996 | Translational Polygon Containment and Minimal Enclosure using Linear Programming Based Restriction. Victor Milenkovic |
| 1996 | Universal Algorithms for Store-and-Forward and Wormhole Routing. Robert Cypher, Friedhelm Meyer auf der Heide, Christian Scheideler, Berthold Vöcking |
| 1996 | Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. Matthew Clegg, Jeff Edmonds, Russell Impagliazzo |
| 1996 | Witness-Based Cryptographic Program Checking and Robust Function Sharing. Yair Frankel, Peter Gemmell, Moti Yung |