| 1995 | Normal Numbers and Sources for BPP. | Martin Strauss |
| 1995 | On the Average Running Time of Odd-Even Merge Sort. | Christine Rb |
| 1995 | On Slender Context-free Languages. | Danny Raz |
| 1995 | The Number of Views of Piecewise-Smooth Algebraic Objects. | Sylvain Petitjean |
| 1995 | Enumerating Extreme Points in Higher Dimensions. | Thomas Ottmann, Sven Schuierer, Subbiah Soundaralakshmi |
| 1995 | Expander Properties in Random Regular Graphs with Edge Faults. | Sotiris E. Nikoletseas, Paul G. Spirakis |
| 1995 | Systolic Tree Omega-Languages. | Angelo Monti, Adriano Peron |
| 1995 | Algorithms Explained by Symmetries. | Torsten Minkwitz |
| 1995 | Concurrent Process Equivalences: Some Decision Problems (Abstract). | Albert R. Meyer |
| 1995 | On the Synthesis of Discrete Controllers for Timed Systems (An Extended Abstract). | Oded Maler, Amir Pnueli, Joseph Sifakis |
| 1995 | On the Structure of Log-Space Probabilistic Complexity Classes (Extended Abstract). | Ioan I. Macarie |
| 1995 | Finding the Maximum with Linear Error Probabilities: A Sequential Analysis Approach. | Guy Louchard |
| 1995 | Optimal Average Case Sorting on Arrays. | Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt, Peter Rossmanith |
| 1995 | Computability of Convex Sets (Extended Abstract). | Martin Kummer, Marcus Schfer |
| 1995 | Structural Complexity of Omega-Automata. | Sriram C. Krishnan, Anuj Puri, Robert K. Brayton |
| 1995 | On Realizing Iterated Multiplication by Small Depth Threshold Circuits. | Matthias Krause |
| 1995 | The Chi-t-Coloring Problem. | Damon Kaller, Arvind Gupta, Thomas C. Shermer |
| 1995 | Completeness and Weak Completeness Under Polynomial-Size Circuits. | David W. Juedes, Jack H. Lutz |
| 1995 | Malign Distributions for Average Case Circuit Complexity. | Andreas Jakoby, Rdiger Reischuk, Christian Schindelhauer |
| 1995 | Optimal Simulation of Automata by Neural Nets. | Piotr Indyk |
| 1995 | On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks. | Juraj Hromkovic, Krzysztof Lorys, Przemyslawa Kanarek, Ralf Klasing, Walter Unger, Hubert Wagener |
| 1995 | Classes of Bounded Counting Type and their Inclusion Relations. | Ulrich Hertrampf |
| 1995 | A Packet Routing Protocol for Arbitrary Networks. | Friedhelm Meyer auf der Heide, Berthold Vcking |
| 1995 | Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations. | Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann |
| 1995 | Pseudorandom Generators and the Frequency of Simplicity. | Yenjo Han, Lane A. Hemaspaandra |