| 1995 | 3-Coloring in Time O(1.3446 Richard Beigel, David Eppstein |
| 1995 | 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, Milwaukee, Wisconsin, USA, 23-25 October 1995 |
| 1995 | A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications. András A. Benczúr |
| 1995 | A Scheduling Model for Reduced CPU Energy. F. Frances Yao, Alan J. Demers, Scott Shenker |
| 1995 | A Unified Analysis of Paging and Caching. Eric Torng |
| 1995 | Algebraic Decompositions of Non-Convex Polyhedra. Herbert Edelsbrunner |
| 1995 | Algorithms for Matrix Groups and the Tits Alternative. Robert Beals |
| 1995 | Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking. Chris Okasaki |
| 1995 | An Approximation Scheme for Planar Graph TSP. Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou |
| 1995 | An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross |
| 1995 | Application-Controlled Paging for a Shared Cache (Extended Abstract). Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter |
| 1995 | Approximability of Flow Shop Scheduling. Leslie A. Hall |
| 1995 | Approximating the Volume of Definable Sets. Pascal Koiran |
| 1995 | Coding for Computing. Alon Orlitsky, James R. Roche |
| 1995 | Cognitive Computation (Extended Abstract). Leslie G. Valiant |
| 1995 | Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version). Amos Fiat, Yishay Mansour, Adi Rosén, Orli Waarts |
| 1995 | Computing Simulations on Finite and Infinite Graphs. Monika Rauch Henzinger, Thomas A. Henzinger, Peter W. Kopke |
| 1995 | Contention Resolution with Bounded Delay. Mike Paterson, Aravind Srinivasan |
| 1995 | Controllability, Recognizability, and Complexity Issues in Robot Motion Planning. Jean-Claude Latombe |
| 1995 | Counting Bottlenecks to Show Monotone P <=> NP. Armin Haken |
| 1995 | Derandomizing Semidefinite Programming Based Approximation Algorithms. Sanjeev Mahajan, Ramesh Hariharan |
| 1995 | Disjoint Paths in Densely Embedded Graphs. Jon M. Kleinberg, Éva Tardos |
| 1995 | Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). Guy Even, Joseph Naor, Satish Rao, Baruch Schieber |
| 1995 | Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings. Milena Mihail, Christos Kaklamanis, Satish Rao |
| 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 | Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems. John H. Reif |
| 1995 | Faster Algorithms for the Construction of Parameterized Suffix Trees (Preliminary Version). S. Rao Kosaraju |
| 1995 | Faster Approximate Agreement with Multi-Writer Registers. Eric Schenk |
| 1995 | Fault Diagnosis in a Flash. Richard Beigel, William Hurwood, Nabil Kahalé |
| 1995 | Finding Points on Curves over Finite Fields (Extended Abstract). Joachim von zur Gathen, Igor E. Shparlinski |
| 1995 | Free Bits, PCPs and Non-Approximability - Towards Tight Results. Mihir Bellare, Oded Goldreich, Madhu Sudan |
| 1995 | Fully Dynamic Biconnectivity and Transitive Closure. Monika Rauch Henzinger, Valerie King |
| 1995 | Gambling in a Rigged Casino: The Adversarial Multi-Arm Bandit Problem. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire |
| 1995 | Hard-Core Distributions for Somewhat Hard Problems. Russell Impagliazzo |
| 1995 | Improved Algorithms and Analysis for Secretary Problems and Generalizations. Miklós Ajtai, Nimrod Megiddo, Orli Waarts |
| 1995 | Improved Depth Lower Vounds for Small Distance Connectivity. Paul Beame, Russell Impagliazzo, Toniann Pitassi |
| 1995 | Improved Hardness Results for Approximating the Chromatic Number. Martin Fürer |
| 1995 | Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1995 | Integral Geometry of Higher-Dimensional Polytopes and the Average Case in Combinatorial Optimization. Alexander I. Barvinok |
| 1995 | Learning Polynomials with Queries: The Highly Noisy Case. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan |
| 1995 | Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). Noga Alon, Jeff Edmonds, Michael Luby |
| 1995 | Linearity Testing in Characteristic Two. Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan |
| 1995 | Load Balancing in the L Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter |
| 1995 | Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). Noam Nisan, Avi Wigderson |
| 1995 | Lower Bounds for Monotone Span Programs. Amos Beimel, Anna Gál, Mike Paterson |
| 1995 | Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). Michael Luby, Dana Randall, Alistair Sinclair |
| 1995 | Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time. C. R. Subramanian |
| 1995 | On Computing Boolean Functions by Sparse Real Polynomials. Matthias Krause, Pavel Pudlák |
| 1995 | On One-Dimensional Quantum Cellular Automata. John Watrous |
| 1995 | Optimal Algorithms for Curves on Surfaces. Tamal K. Dey, Sumanta Guha |
| 1995 | Optimal On-Line Search and Sublinear Time Update in String Matching. Paolo Ferragina, Roberto Grossi |
| 1995 | Perspectives on Database Theory. Mihalis Yannakakis |
| 1995 | Private Information Retrieval. Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan |
| 1995 | Pseudorandom Generators, Measure Theory, and Natural Proofs. Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai |
| 1995 | RSPACE(S) \subseteq DSPACE(S Michael E. Saks, Shiyu Zhou |
| 1995 | Reconstructing Strings from Substrings in Rounds. Dimitris Margaritis, Steven Skiena |
| 1995 | Reductions, Codes, PCPs, and Inapproximability. Sanjeev Arora |
| 1995 | Resolving Message Complexity of Byzantine Agreement and beyond. Zvi Galil, Alain J. Mayer, Moti Yung |
| 1995 | Routing on Butterfly Networks with Random Faults. Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman |
| 1995 | Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. Nader H. Bshouty, Yishay Mansour |
| 1995 | Sparse P-Hard Sets Yield Space-Efficient Algorithms. Mitsunori Ogihara |
| 1995 | Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity. Satyanarayana V. Lokam |
| 1995 | Speed is as Powerful as Clairvoyance. Bala Kalyanasundaram, Kirk Pruhs |
| 1995 | Splitters and Near-Optimal Derandomization. Moni Naor, Leonard J. Schulman, Aravind Srinivasan |
| 1995 | Sublogarithmic Searching without Multiplications. Arne Andersson |
| 1995 | Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions. Moni Naor, Omer Reingold |
| 1995 | The Bit Vector Intersection Problem (Preliminary Version). Richard M. Karp, Orli Waarts, Geoffrey Zweig |
| 1995 | The Loading Time Scheduling Problem (Extended Abstract). Randeep Bhatia, Samir Khuller, Joseph Naor |
| 1995 | The Resolution of a Hartmanis Conjecture. Jin-Yi Cai, D. Sivakumar |
| 1995 | Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines. C. Greg Plaxton |
| 1995 | Tight Fault Locality (Extended Abstract). Shay Kutten, David Peleg |
| 1995 | Tracking the Best Disjunction. Peter Auer, Manfred K. Warmuth |
| 1995 | Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). Sridhar Hannenhalli, Pavel A. Pevzner |
| 1995 | Using Autoreducibility to Separate Complexity Classes. Harry Buhrman, Lance Fortnow, Leen Torenvliet |