| 1995 | Testing multivariate linear functions: overcoming the generator bottleneck. | Funda Ergn |
| 1995 | Geometric lower bounds for parametric matroid optimization. | David Eppstein |
| 1995 | A nearly optimal time-space lower bound for directed | Jeff Edmonds, Chung Keung Poon |
| 1995 | Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract). | Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg |
| 1995 | A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. | Yefim Dinitz, Zeev Nutov |
| 1995 | What do we know about the Metropolis algorithm? | Persi Diaconis, Laurent Saloff-Coste |
| 1995 | Work-time-optimal parallel algorithms for string problems. | Artur Czumaj, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Plandowski |
| 1995 | On real Turing machines that toss coins. | Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther |
| 1995 | Lower bounds for off-line range searching. | Bernard Chazelle |
| 1995 | Bounding the power of preemption in randomized scheduling. | Ran Canetti, Sandy Irani |
| 1995 | On the Fourier spectrum of monotone functions (Extended Abstract). | Nader H. Bshouty, Christino Tamon |
| 1995 | The k-Steiner ratio in graphs. | Al Borchers, Ding-Zhu Du |
| 1995 | Lower bounds for cutting planes proofs with small coefficients. | Maria Luisa Bonet, Toniann Pitassi, Ran Raz |
| 1995 | A constant-factor approximation for the | Avrim Blum, Prasad Chalasani, Santosh S. Vempala |
| 1995 | Provably secure session key distribution: the three party case. | Mihir Bellare, Phillip Rogaway |
| 1995 | Incremental cryptography and application to virus protection. | Mihir Bellare, Oded Goldreich, Shafi Goldwasser |
| 1995 | The relative complexity of NP search problems. | Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi |
| 1995 | More on the complexity of negation-limited circuits. | Robert Beals, Tetsuro Nishino, Keisuke Tanaka |
| 1995 | Bandwidth allocation with preemption. | Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber |
| 1995 | Improved approximation guarantees for minimum-weight | Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala |
| 1995 | Euclidean spanners: short, thin, and lanky. | Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel H. M. Smid |
| 1995 | Polynomial time approximation schemes for dense instances of | Sanjeev Arora, David R. Karger, Marek Karpinski |
| 1995 | A tight lower bound for searching a sorted array. | Arne Andersson, Johan Hstad, Ola Petersson |
| 1995 | Sorting in linear time? | Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman |
| 1995 | Computing faces in segment and simplex arrangements (Preliminary Version). | Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos |