| 1997 | Symbolic Model Checking for Probabilistic Processes. | Christel Baier, Edmund M. Clarke, Vasiliki Hartonas-Garmhausen, Marta Z. Kwiatkowska, Mark Ryan |
| 1997 | On the Dynamics of Sharing Graphs. | Andrea Asperti, Cosimo Laneve |
| 1997 | From Chaotic Iteration to Constraint Propagation. | Krzysztof R. Apt |
| 1997 | Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs. | Alexander E. Andreev, Andrea E. F. Clementi, Jos D. P. Rolim |
| 1997 | Upper Bound on Communication Complexity of Private Information Retrieval. | Andris Ambainis |
| 1997 | Minimizing Diameters of Dynamic Trees. | Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup |
| 1997 | Randomization and Nondeterminism Are Comparable for Ordered Read-Once Branching Programs. | Farid M. Ablayev |
| 1996 | Agent Rendezvous: A Dynamic Symmetry-Breaking Problem. | Xiangdong Yu, Moti Yung |
| 1996 | Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results. | Jir Wiedermann |
| 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 | Semi-Groups Acting on Context-Free Graphs. | Graud Snizergues |
| 1996 | Self-Organizing Data Structures with Dependent Accesses. | Frank Schulz, Elmar Schmer |
| 1996 | Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. | Alexander A. Razborov |
| 1996 | Recognizing Regular Expressions by Means of Dataflow Networks. | Pascal Raymond |
| 1996 | Bandwidth Efficient Parallel Computation. | Abhiram G. Ranade |
| 1996 | The Expressive Power of Existential First Order Sentences of Bchi's Sequential Calculus. | Jean-Eric Pin |
| 1996 | On the Complexity of String Folding. | Mike Paterson, Teresa M. Przytycka |
| 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 | Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. | Peter Bro Miltersen |
| 1996 | Termination of Context-Sensitive Rewriting by Rewriting. | Salvador Lucas |
| 1996 | On Standard Sturmian Morphisms. | Aldo de Luca |
| 1996 | Hard Sets Method and Semilinear Reservoir Method with Applications. | Leonid P. Lisovik |
| 1996 | A Hierarchy Theorem for the µ-Calculus. | Giacomo Lenzi |
| 1996 | Searching a Fixed Graph. | Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis |