| 1996 | "Optimal" Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics. Roberto Giacobazzi |
| 1996 | A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume. Scott A. Mitchell |
| 1996 | A Combinatorial Design Approach to MAXCUT. Thomas Hofmeister, Hanno Lefmann |
| 1996 | A Decision Procedure for Well-Formed Linear Quantum Cellular Automata. Christoph Dürr, Huong Lê Thanh, Miklos Santha |
| 1996 | A Unified and Generalized Treatment of Authentification Theory. Ueli M. Maurer |
| 1996 | An Aperiodic Set of Wang Cubes. Karel Culík II, Jarkko Kari |
| 1996 | Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width. Arvind Gupta, Naomi Nishimura |
| 1996 | Compositional Specification of Timed Systems (Extended Abstract). Joseph Sifakis, Sergio Yovine |
| 1996 | Compressibility and Resource Bounded Measure. Harry Buhrman, Luc Longpré |
| 1996 | Cyclic Languages and Strongly Cyclic Languages. Marie-Pierre Béal, Olivier Carton, Christophe Reutenauer |
| 1996 | Embedding Graphs with Bounded Treewidth into Optimal Hypercubes. Volker Heun, Ernst W. Mayr |
| 1996 | Extracting Best Consensus Motifs from Positive and Negative Examples. Erika Tateishi, Osamu Maruyama, Satoru Miyano |
| 1996 | Fault-Tolerant Shared Memory Simulations. Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann |
| 1996 | Fine Separation of Average Time Complexity Classes. Jin-Yi Cai, Alan L. Selman |
| 1996 | Flip-Flop Nets. Vincent Schmitt |
| 1996 | General Inductive Inference Types Based on Linearly-Ordered Sets. Andris Ambainis, Rusins Freivalds, Carl H. Smith |
| 1996 | Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters. Jens Lagergren |
| 1996 | Languages Recognized by Finite Aperiodic Groupoids. Martin Beaudry |
| 1996 | Learning with Confidence. Janis Barzdins, Rusins Freivalds, Carl H. Smith |
| 1996 | Linear Programming - Randomization and Abstract Frameworks. Bernd Gärtner, Emo Welzl |
| 1996 | Lower Bounds for Compact Routing (Extended Abstract). Evangelos Kranakis, Danny Krizanc |
| 1996 | Lyndon Factorization of Infinite Words. Guy Melançon |
| 1996 | Minimal Forbidden Words and Symbolic Dynamics. Marie-Pierre Béal, Filippo Mignosi, Antonio Restivo |
| 1996 | Monadic Second Order Logic on Tree-Like Structures. Igor Walukiewicz |
| 1996 | New Trends in Quantum Computing. Gilles Brassard |
| 1996 | Observations on Measure and Lowness for Delta^P_2. Jack H. Lutz |
| 1996 | On Bijections vs. Unary Functions. Thomas Schwentick |
| 1996 | On Competitive On-Line Paging with Lookahead. Dany Breslauer |
| 1996 | On Word-Level Parallelism in Fault-Tolerant Computing. Piotr Indyk |
| 1996 | On the Complexity of Random Strings (Extended Abstract). Martin Kummer |
| 1996 | On the Complexity of Worst Case and Expected Time in a Circuit. Andreas Jakoby, Christian Schindelhauer |
| 1996 | On the Existence of Hard Sparse Sets under Weak Reductions. Jin-Yi Cai, Ashish V. Naik, D. Sivakumar |
| 1996 | On the Expressivity of the Modal Mu-Calculus. Julian C. Bradfield |
| 1996 | On the Power of Non-Observable Actions in Timed Automata. Béatrice Bérard, Paul Gastin, Antoine Petit |
| 1996 | On the Successor Function in Non-Classical Numeration Systems. Christiane Frougny |
| 1996 | Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardware. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim |
| 1996 | Optimal Schedules for d-D Grid Graphs with Communication Delays (Extended Abstract). Evripidis Bampis, Charles Delorme, Jean-Claude König |
| 1996 | Optimal Tree-Based One-Time Digital Signature Schemes. Daniel Bleichenbacher, Ueli M. Maurer |
| 1996 | PAC Learning with Simple Examples. François Denis, Cyrille D'Halluin, Rémi Gilleron |
| 1996 | Parallel Comparability Graph Recognition and Modular Decomposition. Michel Morvan, Laurent Viennot |
| 1996 | Ranking and Unranking Trees Using Regular Reductions. Pierre Kelsen |
| 1996 | Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams. Beate Bollig, Ingo Wegener |
| 1996 | Remarks on Generalized Post Correspondence Problem. Tero Harju, Juhani Karhumäki, Daniel Krob |
| 1996 | Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness. Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| 1996 | STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings Claude Puech, Rüdiger Reischuk |
| 1996 | Solvable Black-Box Group Problems Are Low for PP. Vikraman Arvind, N. V. Vinodchandran |
| 1996 | Some Bounds on Multiparty Communication Complexity of Pointer Jumping. Carsten Damm, Stasys Jukna, Jirí Sgall |
| 1996 | Star-Height of an N-Rational Series. Frédérique Bassino |
| 1996 | The "log Rank" Conjecture for Modular Communication Complexity. Christoph Meinel, Stephan Waack |
| 1996 | The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs. Jerzy Marcinkowski |
| 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 | The Complexity of Generating and Checking Proffs of Membership. Harry Buhrman, Thomas Thierauf |
| 1996 | Trace Rewriting: Computing Normal Forms in Time O(n log n). Michael Bertol, Volker Diekert |
| 1996 | Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes. Martin Dietzfelbinger |
| 1996 | Upper Bounds on Multiparty Communication Complexity of Shifts. Andris Ambainis |