| 1995 | Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings. | Milena Mihail, Christos Kaklamanis, Satish Rao |
| 1995 | Reconstructing Strings from Substrings in Rounds. | Dimitris Margaritis, Steven Skiena |
| 1995 | Derandomizing Semidefinite Programming Based Approximation Algorithms. | Sanjeev Mahajan, Ramesh Hariharan |
| 1995 | Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). | Michael Luby, Dana Randall, Alistair Sinclair |
| 1995 | Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity. | Satyanarayana V. Lokam |
| 1995 | Controllability, Recognizability, and Complexity Issues in Robot Motion Planning. | Jean-Claude Latombe |
| 1995 | Tight Fault Locality (Extended Abstract). | Shay Kutten, David Peleg |
| 1995 | On Computing Boolean Functions by Sparse Real Polynomials. | Matthias Krause, Pavel Pudlk |
| 1995 | Faster Algorithms for the Construction of Parameterized Suffix Trees (Preliminary Version). | S. Rao Kosaraju |
| 1995 | Approximating the Volume of Definable Sets. | Pascal Koiran |
| 1995 | Disjoint Paths in Densely Embedded Graphs. | Jon M. Kleinberg, va Tardos |
| 1995 | The Bit Vector Intersection Problem (Preliminary Version). | Richard M. Karp, Orli Waarts, Geoffrey Zweig |
| 1995 | Speed is as Powerful as Clairvoyance. | Bala Kalyanasundaram, Kirk Pruhs |
| 1995 | Hard-Core Distributions for Somewhat Hard Problems. | Russell Impagliazzo |
| 1995 | Fully Dynamic Biconnectivity and Transitive Closure. | Monika Rauch Henzinger, Valerie King |
| 1995 | Computing Simulations on Finite and Infinite Graphs. | Monika Rauch Henzinger, Thomas A. Henzinger, Peter W. Kopke |
| 1995 | Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). | Sridhar Hannenhalli, Pavel A. Pevzner |
| 1995 | Approximability of Flow Shop Scheduling. | Leslie A. Hall |
| 1995 | Counting Bottlenecks to Show Monotone P <=> NP. | Armin Haken |
| 1995 | Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. | Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1995 | An Approximation Scheme for Planar Graph TSP. | Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou |
| 1995 | Learning Polynomials with Queries: The Highly Noisy Case. | Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan |
| 1995 | Finding Points on Curves over Finite Fields (Extended Abstract). | Joachim von zur Gathen, Igor E. Shparlinski |
| 1995 | Resolving Message Complexity of Byzantine Agreement and beyond. | Zvi Galil, Alain J. Mayer, Moti Yung |
| 1995 | Improved Hardness Results for Approximating the Chromatic Number. | Martin Frer |