| 1995 | Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). | Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp |
| 1995 | Finding Largest Common Embeddable Subtrees. | Arvind Gupta, Naomi Nishimura |
| 1995 | Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates. | Frederic Green |
| 1995 | Deterministic Generalized Automata. | Dora Giammarresi, Rosa Montalbano |
| 1995 | On the Separators on an Infinite Word Generated by a Morphism. | Emmanuelle Garel |
| 1995 | Dynamic Analysis of the Sizes of Relations. | Danile Gardy, Guy Louchard |
| 1995 | Resource-Bounded Instance Complexity (Extended Abstract). | Lance Fortnow, Martin Kummer |
| 1995 | Interval Routing Schemes. | Michele Flammini, Giorgio Gambosi, Sandro Salomone |
| 1995 | Generalized Scans and Tri-Diagonal Systems. | Paul F. Fischer, Franco P. Preparata, John E. Savage |
| 1995 | Beyond P^(NP) - NEXP. | Stephen A. Fenner, Lance Fortnow |
| 1995 | On the Subword Equivalence Problem for Infinite Words. | Isabelle Fagnot |
| 1995 | On the Undecidability of Deadlock Detection in Families of Nets. | Anne-Ccile Fabret, Antoine Petit |
| 1995 | Optimal Lower Bounds on the Multiparty Communication Complexity. | Pavol Duris, Jos D. P. Rolim |
| 1995 | A Random NP-Complete Problem for Inversion of 2D Cellular Automata. | Bruno Durand |
| 1995 | On-line and Dynamic Algorithms for Shorted Path Problems. | Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis |
| 1995 | On Codings of Traces. | Volker Diekert, Anca Muscholl, Klaus Reinhardt |
| 1995 | Line Segmentation of Digital Curves in Parallel. | Peter Damaschke |
| 1995 | A Set-Theoretic Translation Method for (Poly)modal Logics. | Giovanna D'Agostino, Angelo Montanari, Alberto Policriti |
| 1995 | Two-Dimensional Pattern Matching in Linear Time and Small Space. | Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter |
| 1995 | Communication Complexity of Key Agreement on Small Ranges. | Jin-yi Cai, Richard J. Lipton, Luc Longpr, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar |
| 1995 | On Compact Representations of Propositional Circumscription. | Marco Cadoli, Francesco M. Donini, Marco Schaerf |
| 1995 | Growing Context-Sensitive Languages and Church-Rosser Languages. | Gerhard Buntrock, Friedrich Otto |
| 1995 | On the Sparse Set Conjecture for Sets with Low Denisty. | Harry Buhrman, Montserrat Hermo |
| 1995 | Coding and Strong Coding in Trace Monoids. | Vronique Bruyre, Clelia de Felice |
| 1995 | Dependence Orders for Computations of Concurrent Automata. | Felipe Bracho, Manfred Droste, Dietrich Kuske |