| 1996 | An Aperiodic Set of Wang Cubes. | Karel Culk II, Jarkko Kari |
| 1996 | Fine Separation of Average Time Complexity Classes. | Jin-yi Cai, Alan L. Selman |
| 1996 | On the Existence of Hard Sparse Sets under Weak Reductions. | Jin-yi Cai, Ashish V. Naik, D. Sivakumar |
| 1996 | The Complexity of Generating and Checking Proffs of Membership. | Harry Buhrman, Thomas Thierauf |
| 1996 | Compressibility and Resource Bounded Measure. | Harry Buhrman, Luc Longpr |
| 1996 | On Competitive On-Line Paging with Lookahead. | Dany Breslauer |
| 1996 | New Trends in Quantum Computing. | Gilles Brassard |
| 1996 | On the Expressivity of the Modal Mu-Calculus. | Julian C. Bradfield |
| 1996 | Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams. | Beate Bollig, Ingo Wegener |
| 1996 | Optimal Tree-Based One-Time Digital Signature Schemes. | Daniel Bleichenbacher, Ueli M. Maurer |
| 1996 | Trace Rewriting: Computing Normal Forms in Time O(n log n). | Michael Bertol, Volker Diekert |
| 1996 | Fault-Tolerant Shared Memory Simulations. | Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann |
| 1996 | On the Power of Non-Observable Actions in Timed Automata. | Batrice Brard, Paul Gastin, Antoine Petit |
| 1996 | Languages Recognized by Finite Aperiodic Groupoids. | Martin Beaudry |
| 1996 | Minimal Forbidden Words and Symbolic Dynamics. | Marie-Pierre Bal, Filippo Mignosi, Antonio Restivo |
| 1996 | Cyclic Languages and Strongly Cyclic Languages. | Marie-Pierre Bal, Olivier Carton, Christophe Reutenauer |
| 1996 | Star-Height of an N-Rational Series. | Frdrique Bassino |
| 1996 | Learning with Confidence. | Janis Barzdins, Rusins Freivalds, Carl H. Smith |
| 1996 | Optimal Schedules for d-D Grid Graphs with Communication Delays (Extended Abstract). | Evripidis Bampis, Charles Delorme, Jean-Claude Knig |
| 1996 | Solvable Black-Box Group Problems Are Low for PP. | Vikraman Arvind, N. V. Vinodchandran |
| 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 | Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness. | Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| 1996 | General Inductive Inference Types Based on Linearly-Ordered Sets. | Andris Ambainis, Rusins Freivalds, Carl H. Smith |
| 1996 | Upper Bounds on Multiparty Communication Complexity of Shifts. | Andris Ambainis |
| 1995 | On the Synthesis of Strategies in Infinite Games. | Wolfgang Thomas |