| 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 | A Delaunay based numerical method for three dimensions: generation, formulation, and partition. Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington |
| 1995 | A computational view of population genetics. Yuval Rabani, Yuri Rabinovich, Alistair Sinclair |
| 1995 | A constant-factor approximation for the Avrim Blum, Prasad Chalasani, Santosh S. Vempala |
| 1995 | A fully-dynamic data structure for external substring search (Extended Abstract). Paolo Ferragina, Roberto Grossi |
| 1995 | A lower bound for integer multiplication with read-once branching programs. Stephen Ponzio |
| 1995 | A nearly optimal time-space lower bound for directed Jeff Edmonds, Chung Keung Poon |
| 1995 | A parallel repetition theorem. Ran Raz |
| 1995 | A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. David R. Karger |
| 1995 | A tight lower bound for searching a sorted array. Arne Andersson, Johan Håstad, Ola Petersson |
| 1995 | Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. David R. Karger, Serge A. Plotkin |
| 1995 | Additive versus exponentiated gradient updates for linear prediction. Jyrki Kivinen, Manfred K. Warmuth |
| 1995 | Approximations for the disjoint paths problem in high-diameter planar networks. Jon M. Kleinberg, Éva Tardos |
| 1995 | Average-case completeness of a word problem for groups. Jie Wang |
| 1995 | Bandwidth allocation with preemption. Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber |
| 1995 | Bounding delays in packet-routing networks. Mor Harchol-Balter, David Wolfe |
| 1995 | Bounding the power of preemption in randomized scheduling. Ran Canetti, Sandy Irani |
| 1995 | Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract). Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg |
| 1995 | Computing faces in segment and simplex arrangements (Preliminary Version). Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos |
| 1995 | Descriptive complexity theory over the real numbers. Erich Grädel, Klaus Meer |
| 1995 | Distinguishing tests for nondeterministic and probabilistic machines. Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis |
| 1995 | Efficient stopping rules for Markov chains. László Lovász, Peter Winkler |
| 1995 | Euclidean spanners: short, thin, and lanky. Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel H. M. Smid |
| 1995 | Explicit dispersers with polylog degree. Michael E. Saks, Aravind Srinivasan, Shiyu Zhou |
| 1995 | Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (Extended Abstract). William E. Hart, Sorin Istrail |
| 1995 | Geometric lower bounds for parametric matroid optimization. David Eppstein |
| 1995 | How many queries are needed to learn? Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins |
| 1995 | Impossibility results for recycling random bits in two-prover proof systems. Uriel Feige, Joe Kilian |
| 1995 | Improved approximation algorithms for uniform connectivity problems. Samir Khuller, Balaji Raghavachari |
| 1995 | Improved approximation guarantees for minimum-weight Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala |
| 1995 | Improved approximations of packing and covering problems. Aravind Srinivasan |
| 1995 | Incremental cryptography and application to virus protection. Mihir Bellare, Oded Goldreich, Shafi Goldwasser |
| 1995 | Knowledge on the average-perfect, statistical and logarithmic. William Aiello, Mihir Bellare, Ramarathnam Venkatesan |
| 1995 | Large-scale assembly of DNA strings and space-efficient construction of suffix trees. S. Rao Kosaraju, Arthur L. Delcher |
| 1995 | Linear-time encodable and decodable error-correcting codes. Daniel A. Spielman |
| 1995 | Log-space polynomial end-to-end communication. Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén |
| 1995 | Lower bounds for cutting planes proofs with small coefficients. Maria Luisa Bonet, Toniann Pitassi, Ran Raz |
| 1995 | Lower bounds for off-line range searching. Bernard Chazelle |
| 1995 | Lower bounds for sorting networks. Nabil Kahalé, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi |
| 1995 | Many-to-one packet routing on grids (Extended Abstract). Yishay Mansour, Boaz Patt-Shamir |
| 1995 | Monotone circuits for connectivity have depth (log n) Mikael Goldmann, Johan Håstad |
| 1995 | More on the complexity of negation-limited circuits. Robert Beals, Tetsuro Nishino, Keisuke Tanaka |
| 1995 | Motion planning for a steering-constrained robot through moderate obstacles. Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki |
| 1995 | On data structures and asymmetric communication complexity. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson |
| 1995 | On randomized one-round communication complexity. Ilan Kremer, Noam Nisan, Dana Ron |
| 1995 | On real Turing machines that toss coins. Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther |
| 1995 | On the Fourier spectrum of monotone functions (Extended Abstract). Nader H. Bshouty, Christino Tamon |
| 1995 | On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. Noam Nisan, Avi Wigderson |
| 1995 | Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. Victor Y. Pan |
| 1995 | Parallel randomized load balancing (Preliminary Version). Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Eilstrup Rasmussen |
| 1995 | Persistent lists with catenation via recursive slow-down. Haim Kaplan, Robert Endre Tarjan |
| 1995 | Polynomial bounds for VC dimension of sigmoidal neural networks. Marek Karpinski, Angus Macintyre |
| 1995 | Polynomial time approximation schemes for dense instances of Sanjeev Arora, David R. Karger, Marek Karpinski |
| 1995 | Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA Frank Thomson Leighton, Allan Borodin |
| 1995 | Provably secure session key distribution: the three party case. Mihir Bellare, Phillip Rogaway |
| 1995 | Randomized and multipointer paging with locality of reference. Amos Fiat, Anna R. Karlin |
| 1995 | Randomized dynamic graph algorithms with polylogarithmic time per operation. Monika Rauch Henzinger, Valerie King |
| 1995 | Randomized graph products, chromatic numbers, and Lovasz theta-function. Uriel Feige |
| 1995 | Randomized query processing in robot path planning (Extended Abstract). Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan |
| 1995 | Recognition of graphs with threshold dimension two. Thomas Raschle, Klaus Simon |
| 1995 | Secure hypergraphs: privacy from partial broadcast (Extended Abstract). Matthew K. Franklin, Moti Yung |
| 1995 | Security of quantum protocols against coherent measurements. Andrew Chi-Chih Yao |
| 1995 | Short length versions of Menger's theorem (Extended Abstract). Zvi Galil, Xiangdong Yu |
| 1995 | Sorting in linear time? Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman |
| 1995 | Stochastic contention resolution with short delays. Prabhakar Raghavan, Eli Upfal |
| 1995 | String matching in Lempel-Ziv compressed strings. Martin Farach, Mikkel Thorup |
| 1995 | Subquadratic-time factoring of polynomials over finite fields. Erich L. Kaltofen, Victor Shoup |
| 1995 | Symmetric logspace is closed under complement. Noam Nisan, Amnon Ta-Shma |
| 1995 | Testing multivariate linear functions: overcoming the generator bottleneck. Funda Ergün |
| 1995 | The k-Steiner ratio in graphs. Al Borchers, Ding-Zhu Du |
| 1995 | The relative complexity of NP search problems. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi |
| 1995 | Tight analyses of two local load balancing algorithms. Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman |
| 1995 | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Sridhar Hannenhalli, Pavel A. Pevzner |
| 1995 | Two Steiner tree packing problems (Extended Abstract). William R. Pulleyblank |
| 1995 | Wait-free made fast (Extended Abstract). Yehuda Afek, Dalia Dauber, Dan Touitou |
| 1995 | What do we know about the Metropolis algorithm? Persi Diaconis, Laurent Saloff-Coste |
| 1995 | What's decidable about hybrid automata? Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya |
| 1995 | Work efficient parallel solution of Toeplitz systems and polynomial GCD. John H. Reif |
| 1995 | Work-time-optimal parallel algorithms for string problems. Artur Czumaj, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Plandowski |