| 1995 | Some Typical Properties of Large AND/OR Boolean Formulas. | Hanno Lefmann, Petr Savick |
| 1995 | From Timed Automata to Logic - and Back. | Franois Laroussinie, Kim Guldstrand Larsen, Carsten Weise |
| 1995 | String Recognition on Anonymous Rings. | Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio |
| 1995 | On a Quantitative Notion of Uniformity. | Susanne Kaufmann, Martin Kummer |
| 1995 | Asymptotically Efficient In-Place Merging. | Jyrki Katajainen, Tomi Pasanen, George Titan |
| 1995 | Strong Lower Bounds on the Approximability of some NPO PB-Complete Maximization Problems. | Viggo Kann |
| 1995 | Automata for the Modal mu-Calculus and related Results. | David Janin, Igor Walukiewicz |
| 1995 | The Hedge: An Efficient Storage Device for Turing Machines with One Head (Extended Abstract). | Martin Hhne |
| 1995 | Modular Constructions of Distributing Automata. | Sbastien Huguet, Antoine Petit |
| 1995 | A New Approach to Analyse Coupled-Context-Free Languages. | Gnter Hotz, Gisela Pitsch |
| 1995 | Nonuniform Lower Bounds for Exponential Time Classes. | Steven Homer, Sarah Mocas |
| 1995 | Derandomization for Sparse Approximations and Independent Sets. | Thomas Hofmeister, Hanno Lefmann |
| 1995 | The Complexity of the Falsifiability Problem for Pure Implicational Formulas. | Peter Heusch |
| 1995 | Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract). | Miki Hermann, Phokion G. Kolaitis |
| 1995 | On the Computing Paradigm and Computational Complexity. | Juris Hartmanis |
| 1995 | Second Order Logic and the Weak Exponential Hierarchies. | Georg Gottlob, Nicola Leone, Helmut Veith |
| 1995 | Syntax and Semantics of Procol. | Roel van der Goot, Arie de Bruin |
| 1995 | Synthesizing Distinguishing Formulae for Real Time Systems (Extended Abstract). | Jens Chr. Godskesen, Kim Guldstrand Larsen |
| 1995 | Bridging Across the log(n) Space Frontier. | Viliam Geffert |
| 1995 | The Complexity of Interval Routing on Random Graphs. | Michele Flammini, Jan van Leeuwen, Alberto Marchetti-Spaccamela |
| 1995 | Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). | Sophie Fischer, Lane A. Hemaspaandra, Leen Torenvliet |
| 1995 | Towards a Semantic Theory of CML (Extended Abstract). | William Ferreira, Matthew Hennessy |
| 1995 | An Operator Calculus Approach to the Evolution of Dynamic Data Structures. | Philip Feinsilver, Ren Schott |
| 1995 | Automata That Take Advice. | Carsten Damm, Markus Holzer |
| 1995 | Performance Preorder: Ordering Processes with Respect to Speed. | Flavio Corradini, Roberto Gorrieri, Marco Roccetti |