| 1996 | A Complete Gentzen-Style Axiomatization for Set Constraints. Allan Cheng, Dexter Kozen |
| 1996 | A Formal Framework for Evaluating Heuristic Programs. Lenore Cowen, Joan Feigenbaum, Sampath Kannan |
| 1996 | A Hierarchy Theorem for the µ-Calculus. Giacomo Lenzi |
| 1996 | A Polynomial-Time Algorithm for Near-Perfect Phylogeny. David Fernández-Baca, Jens Lagergren |
| 1996 | Agent Rendezvous: A Dynamic Symmetry-Breaking Problem. Xiangdong Yu, Moti Yung |
| 1996 | Algebraic Characterizations of Decorated Trace Equivalences over Tree-Like Structures. Xiao Jun Chen, Rocco De Nicola |
| 1996 | An Effective Tableau System for the Linear Time µ-Calculus. Julian C. Bradfield, Javier Esparza, Angelika Mader |
| 1996 | Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings Friedhelm Meyer auf der Heide, Burkhard Monien |
| 1996 | Average Case Analyses of List Update Algorithms, with Applications to Data Compression. Susanne Albers, Michael Mitzenmacher |
| 1996 | Bandwidth Efficient Parallel Computation. Abhiram G. Ranade |
| 1996 | Characterizing Fairness Implementability for Multiparty Interaction. Yuh-Jzer Joung |
| 1996 | Constructions and Bounds for Visual Cryptography. Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson |
| 1996 | Deciding Finiteness of Petri Nets Up To Bisimulation. Petr Jancar, Javier Esparza |
| 1996 | Different Types of Arrow Between Logical Frameworks. Till Mossakowski |
| 1996 | Effective Models of Polymorphism, Subtyping and Recursion (Extended Abstract). John C. Mitchell, Ramesh Viswanathan |
| 1996 | Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler. Yonatan Aumann, Michael A. Bender |
| 1996 | Efficient Collective Communication in Optical Networks. Jean-Claude Bermond, Luisa Gargano, Stephane Perennes, Adele A. Rescigno, Ugo Vaccaro |
| 1996 | Fast Asynchronous Systems in Dense Time. Lars Jenner, Walter Vogler |
| 1996 | Fast Deterministic Backtrack Search. Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci |
| 1996 | Fatal Errors in Conditional Expressions (Extended Abstract). Michel Billaud |
| 1996 | Fixpoints for Rabin Tree Automata Make Complementation Easy. Roope Kaivola |
| 1996 | Hard Sets Method and Semilinear Reservoir Method with Applications. Leonid P. Lisovik |
| 1996 | Hitting Sets Derandomize BPP. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim |
| 1996 | Improved Parallel Approximation of a Class of Integer Programming Programming Problems. Noga Alon, Aravind Srinivasan |
| 1996 | Improved Sampling with Applications to Dynamic Graph Algorithms. Monika Rauch Henzinger, Mikkel Thorup |
| 1996 | Improved Scheduling Algorithms for Minsum Criteria. Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein |
| 1996 | Lopsided Trees: Analyses, Algorithms, and Applications. Vicky Siu-Ngan Choi, Mordecai J. Golin |
| 1996 | Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. Alexander A. Razborov |
| 1996 | Lower Bounds for Row Minima Searching (Extended Abstract). Phillip G. Bradford, Knut Reinert |
| 1996 | Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. Peter Bro Miltersen |
| 1996 | Minimum Fill-In on Circle and Circular-Arc Graphs. Ton Kloks, Dieter Kratsch, C. K. Wong |
| 1996 | Mobile Processes with a Distributed Environment. Chiara Bodei, Pierpaolo Degano, Corrado Priami |
| 1996 | New Upper Bounds to the Limitedness of Distance Automata. Kosaburo Hashiguchi |
| 1996 | On Capital Investment. Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén |
| 1996 | On Infinite Transition Graphs Having a Decidable Monadic Theory. Didier Caucal |
| 1996 | On Standard Sturmian Morphisms. Aldo de Luca |
| 1996 | On Type-2 Probabilistic Quantifiers. Ronald V. Book, Heribert Vollmer, Klaus W. Wagner |
| 1996 | On \omega-Generators and Codes. Sandrine Julia |
| 1996 | On the Complexity of Relational Problems for Finite State Processes (Extended Abstract). Sandeep K. Shukla, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns |
| 1996 | On the Complexity of String Folding. Mike Paterson, Teresa M. Przytycka |
| 1996 | On the Power of Randomized Branching Programs. Farid M. Ablayev, Marek Karpinski |
| 1996 | Optimal Gröbner Base Algorithms for Binomial Ideals. Ulla Koppenhagen, Ernst W. Mayr |
| 1996 | Optimal Logarithmic Time Randomized Suffix Tree Construction. Martin Farach, S. Muthukrishnan |
| 1996 | Practical Approximation Schemes for Maximum Induced-Subgraph Problems on K_{3, 3}-free or K_5-free Graphs. Zhi-Zhong Chen |
| 1996 | Random Polynomials and Polynomial Factorization. Philippe Flajolet, Xavier Gourdon, Daniel Panario |
| 1996 | Recognizing Regular Expressions by Means of Dataflow Networks. Pascal Raymond |
| 1996 | Regularity for a Large Class of Context-Free Processes is Decidable. D. J. B. Bosscher, W. O. David Griffioen |
| 1996 | Saturation-Based Theorem Proving (Abstract). Harald Ganzinger |
| 1996 | Searching a Fixed Graph. Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1996 | Self-Organizing Data Structures with Dependent Accesses. Frank Schulz, Elmar Schömer |
| 1996 | Semi-Groups Acting on Context-Free Graphs. Géraud Sénizergues |
| 1996 | Shared-Memory Simulations on a Faulty-Memory DMM. Bogdan S. Chlebus, Anna Gambin, Piotr Indyk |
| 1996 | Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results. Jirí Wiedermann |
| 1996 | Termination of Context-Sensitive Rewriting by Rewriting. Salvador Lucas |
| 1996 | The Expressive Power of Existential First Order Sentences of Büchi's Sequential Calculus. Jean-Eric Pin |
| 1996 | The Meaning of Negative Premises in Transition System Specifications II. Rob J. van Glabbeek |
| 1996 | Variable-Length Maximal Codes. Véronique Bruyère, Michel Latteux |