| 1996 | Optimal Grbner Base Algorithms for Binomial Ideals. | Ulla Koppenhagen, Ernst W. Mayr |
| 1996 | Minimum Fill-In on Circle and Circular-Arc Graphs. | Ton Kloks, Dieter Kratsch, C. K. Wong |
| 1996 | Fixpoints for Rabin Tree Automata Make Complementation Easy. | Roope Kaivola |
| 1996 | On \omega-Generators and Codes. | Sandrine Julia |
| 1996 | Characterizing Fairness Implementability for Multiparty Interaction. | Yuh-Jzer Joung |
| 1996 | Fast Asynchronous Systems in Dense Time. | Lars Jenner, Walter Vogler |
| 1996 | Deciding Finiteness of Petri Nets Up To Bisimulation. | Petr Jancar, Javier Esparza |
| 1996 | Fast Deterministic Backtrack Search. | Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci |
| 1996 | Improved Sampling with Applications to Dynamic Graph Algorithms. | Monika Rauch Henzinger, Mikkel Thorup |
| 1996 | New Upper Bounds to the Limitedness of Distance Automata. | Kosaburo Hashiguchi |
| 1996 | The Meaning of Negative Premises in Transition System Specifications II. | Rob J. van Glabbeek |
| 1996 | Saturation-Based Theorem Proving (Abstract). | Harald Ganzinger |
| 1996 | Random Polynomials and Polynomial Factorization. | Philippe Flajolet, Xavier Gourdon, Daniel Panario |
| 1996 | A Polynomial-Time Algorithm for Near-Perfect Phylogeny. | David Fernndez-Baca, Jens Lagergren |
| 1996 | Optimal Logarithmic Time Randomized Suffix Tree Construction. | Martin Farach, S. Muthukrishnan |
| 1996 | A Formal Framework for Evaluating Heuristic Programs. | Lenore Cowen, Joan Feigenbaum, Sampath Kannan |
| 1996 | Lopsided Trees: Analyses, Algorithms, and Applications. | Vicky Siu-Ngan Choi, Mordecai J. Golin |
| 1996 | Shared-Memory Simulations on a Faulty-Memory DMM. | Bogdan S. Chlebus, Anna Gambin, Piotr Indyk |
| 1996 | Algebraic Characterizations of Decorated Trace Equivalences over Tree-Like Structures. | Xiao Jun Chen, Rocco De Nicola |
| 1996 | A Complete Gentzen-Style Axiomatization for Set Constraints. | Allan Cheng, Dexter Kozen |
| 1996 | Practical Approximation Schemes for Maximum Induced-Subgraph Problems on K_{3, 3}-free or K_5-free Graphs. | Zhi-Zhong Chen |
| 1996 | Improved Scheduling Algorithms for Minsum Criteria. | Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein |
| 1996 | On Infinite Transition Graphs Having a Decidable Monadic Theory. | Didier Caucal |
| 1996 | Variable-Length Maximal Codes. | Vronique Bruyre, Michel Latteux |
| 1996 | Lower Bounds for Row Minima Searching (Extended Abstract). | Phillip G. Bradford, Knut Reinert |