| 1996 | Parallel Comparability Graph Recognition and Modular Decomposition. | Michel Morvan, Laurent Viennot |
| 1996 | A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume. | Scott A. Mitchell |
| 1996 | Lyndon Factorization of Infinite Words. | Guy Melanon |
| 1996 | The "log Rank" Conjecture for Modular Communication Complexity. | Christoph Meinel, Stephan Waack |
| 1996 | A Unified and Generalized Treatment of Authentification Theory. | Ueli M. Maurer |
| 1996 | The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs. | Jerzy Marcinkowski |
| 1996 | Observations on Measure and Lowness for Delta^P_2. | Jack H. Lutz |
| 1996 | Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters. | Jens Lagergren |
| 1996 | On the Complexity of Random Strings (Extended Abstract). | Martin Kummer |
| 1996 | Lower Bounds for Compact Routing (Extended Abstract). | Evangelos Kranakis, Danny Krizanc |
| 1996 | Ranking and Unranking Trees Using Regular Reductions. | Pierre Kelsen |
| 1996 | On the Complexity of Worst Case and Expected Time in a Circuit. | Andreas Jakoby, Christian Schindelhauer |
| 1996 | On Word-Level Parallelism in Fault-Tolerant Computing. | Piotr Indyk |
| 1996 | A Combinatorial Design Approach to MAXCUT. | Thomas Hofmeister, Hanno Lefmann |
| 1996 | Embedding Graphs with Bounded Treewidth into Optimal Hypercubes. | Volker Heun, Ernst W. Mayr |
| 1996 | Remarks on Generalized Post Correspondence Problem. | Tero Harju, Juhani Karhumki, Daniel Krob |
| 1996 | Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width. | Arvind Gupta, Naomi Nishimura |
| 1996 | "Optimal" Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics. | Roberto Giacobazzi |
| 1996 | Linear Programming - Randomization and Abstract Frameworks. | Bernd Grtner, Emo Welzl |
| 1996 | On the Successor Function in Non-Classical Numeration Systems. | Christiane Frougny |
| 1996 | The Action of a Few Random Permutations on r-Tuples and an Application to Cryptography. | Joel Friedman, Antoine Joux, Yuval Roichman, Jacques Stern, Jean-Pierre Tillich |
| 1996 | A Decision Procedure for Well-Formed Linear Quantum Cellular Automata. | Christoph Drr, Huong L Thanh, Miklos Santha |
| 1996 | Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes. | Martin Dietzfelbinger |
| 1996 | PAC Learning with Simple Examples. | Franois Denis, Cyrille D'Halluin, Rmi Gilleron |
| 1996 | Some Bounds on Multiparty Communication Complexity of Pointer Jumping. | Carsten Damm, Stasys Jukna, Jir Sgall |