| 1995 | Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries. | Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire |
| 1995 | Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version). | Amos Fiat, Yishay Mansour, Adi Rosn, Orli Waarts |
| 1995 | Optimal On-Line Search and Sublinear Time Update in String Matching. | Paolo Ferragina, Roberto Grossi |
| 1995 | Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). | Guy Even, Joseph Naor, Satish Rao, Baruch Schieber |
| 1995 | Algebraic Decompositions of Non-Convex Polyhedra. | Herbert Edelsbrunner |
| 1995 | Optimal Algorithms for Curves on Surfaces. | Tamal K. Dey, Sumanta Guha |
| 1995 | An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). | Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross |
| 1995 | Routing on Butterfly Networks with Random Faults. | Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman |
| 1995 | Private Information Retrieval. | Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan |
| 1995 | The Resolution of a Hartmanis Conjecture. | Jin-yi Cai, D. Sivakumar |
| 1995 | Using Autoreducibility to Separate Complexity Classes. | Harry Buhrman, Lance Fortnow, Leen Torenvliet |
| 1995 | Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. | Nader H. Bshouty, Yishay Mansour |
| 1995 | The Loading Time Scheduling Problem (Extended Abstract). | Randeep Bhatia, Samir Khuller, Joseph Naor |
| 1995 | A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications. | Andrs A. Benczr |
| 1995 | Free Bits, PCPs and Non-Approximability - Towards Tight Results. | Mihir Bellare, Oded Goldreich, Madhu Sudan |
| 1995 | Linearity Testing in Characteristic Two. | Mihir Bellare, Don Coppersmith, Johan Hstad, Marcos A. Kiwi, Madhu Sudan |
| 1995 | Lower Bounds for Monotone Span Programs. | Amos Beimel, Anna Gl, Mike Paterson |
| 1995 | Fault Diagnosis in a Flash. | Richard Beigel, William Hurwood, Nabil Kahal |
| 1995 | 3-Coloring in Time O(1.3446 | Richard Beigel, David Eppstein |
| 1995 | Improved Depth Lower Vounds for Small Distance Connectivity. | Paul Beame, Russell Impagliazzo, Toniann Pitassi |
| 1995 | Algorithms for Matrix Groups and the Tits Alternative. | Robert Beals |
| 1995 | Integral Geometry of Higher-Dimensional Polytopes and the Average Case in Combinatorial Optimization. | Alexander I. Barvinok |
| 1995 | Application-Controlled Paging for a Shared Cache (Extended Abstract). | Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter |
| 1995 | Load Balancing in the L | Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter |
| 1995 | Tracking the Best Disjunction. | Peter Auer, Manfred K. Warmuth |