| 1995 | Additive versus exponentiated gradient updates for linear prediction. | Jyrki Kivinen, Manfred K. Warmuth |
| 1995 | Improved approximation algorithms for uniform connectivity problems. | Samir Khuller, Balaji Raghavachari |
| 1995 | Randomized query processing in robot path planning (Extended Abstract). | Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan |
| 1995 | Polynomial bounds for VC dimension of sigmoidal neural networks. | Marek Karpinski, Angus Macintyre |
| 1995 | Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. | David R. Karger, Serge A. Plotkin |
| 1995 | A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. | David R. Karger |
| 1995 | Persistent lists with catenation via recursive slow-down. | Haim Kaplan, Robert Endre Tarjan |
| 1995 | Subquadratic-time factoring of polynomials over finite fields. | Erich L. Kaltofen, Victor Shoup |
| 1995 | Lower bounds for sorting networks. | Nabil Kahal, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerdi |
| 1995 | What's decidable about hybrid automata? | Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya |
| 1995 | Randomized dynamic graph algorithms with polylogarithmic time per operation. | Monika Rauch Henzinger, Valerie King |
| 1995 | How many queries are needed to learn? | Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins |
| 1995 | Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (Extended Abstract). | William E. Hart, Sorin Istrail |
| 1995 | Bounding delays in packet-routing networks. | Mor Harchol-Balter, David Wolfe |
| 1995 | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. | Sridhar Hannenhalli, Pavel A. Pevzner |
| 1995 | Descriptive complexity theory over the real numbers. | Erich Grdel, Klaus Meer |
| 1995 | Monotone circuits for connectivity have depth (log n) | Mikael Goldmann, Johan Hstad |
| 1995 | Tight analyses of two local load balancing algorithms. | Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andra W. Richa, Robert Endre Tarjan, David Zuckerman |
| 1995 | Short length versions of Menger's theorem (Extended Abstract). | Zvi Galil, Xiangdong Yu |
| 1995 | Secure hypergraphs: privacy from partial broadcast (Extended Abstract). | Matthew K. Franklin, Moti Yung |
| 1995 | Randomized and multipointer paging with locality of reference. | Amos Fiat, Anna R. Karlin |
| 1995 | A fully-dynamic data structure for external substring search (Extended Abstract). | Paolo Ferragina, Roberto Grossi |
| 1995 | Impossibility results for recycling random bits in two-prover proof systems. | Uriel Feige, Joe Kilian |
| 1995 | Randomized graph products, chromatic numbers, and Lovasz theta-function. | Uriel Feige |
| 1995 | String matching in Lempel-Ziv compressed strings. | Martin Farach, Mikkel Thorup |