| 1996 | Towards a Syntactic Characterization of PTAS. | Sanjeev Khanna, Rajeev Motwani |
| 1996 | Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. | Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger |
| 1996 | On the Boosting Ability of Top-Down Decision Tree Learning Algorithms. | Michael J. Kearns, Yishay Mansour |
| 1996 | How Good is the Goemans-Williamson MAX CUT Algorithm? | Howard J. Karloff |
| 1996 | Minimum Cuts in Near-Linear Time. | David R. Karger |
| 1996 | Sparsity Considerations in Dixon Resultants. | Deepak Kapur, Tushar Saxena |
| 1996 | Purely Functional Representations of Catenable Sorted Lists. | Haim Kaplan, Robert Endre Tarjan |
| 1996 | Nondeterministic Communication with a Limited Number of Advice Bits. | Juraj Hromkovic, Georg Schnitger |
| 1996 | Testing of the Long Code and Hardness for Clique. | Johan Hstad |
| 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 | Communication-Efficient Parallel Sorting (Preliminary Version). | Michael T. Goodrich |
| 1996 | Modular Coloring Formulas Are Hard for Cutting Planes Proofs. | Xudong Fu |
| 1996 | Computing Betti Numbers via Combinatorial Laplacians. | Joel Friedman |
| 1996 | Witness-Based Cryptographic Program Checking and Robust Function Sharing. | Yair Frankel, Peter Gemmell, Moti Yung |
| 1996 | A Threshold of ln | Uriel Feige |
| 1996 | Efficient Algorithms for Inverting Evolution. | Martin Farach, Sampath Kannan |
| 1996 | Lower Bounds for Noisy Boolean Decision Trees. | William S. Evans, Nicholas Pippenger |
| 1996 | Digital Signets: Self-Enforcing Protection of Digital Information (Preliminary Version). | Cynthia Dwork, Jeffrey B. Lotspiech, Moni Naor |
| 1996 | Towards an Analysis of Local Optimization Algorithms. | Tassos Dimitriou, Russell Impagliazzo |
| 1996 | Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space (Preliminary Version). | Tamal K. Dey, Sumanta Guha |
| 1996 | Universal Algorithms for Store-and-Forward and Wormhole Routing. | Robert Cypher, Friedhelm Meyer auf der Heide, Christian Scheideler, Berthold Vcking |
| 1996 | Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. | Matthew Clegg, Jeff Edmonds, Russell Impagliazzo |
| 1996 | Fast Algorithms for | Joseph Cheriyan, Ramakrishna Thurimella |
| 1996 | Deterministic Restrictions in Circuit Complexity. | Shiva Chaudhuri, Jaikumar Radhakrishnan |