| 1995 | Gambling in a Rigged Casino: The Adversarial Multi-Arm Bandit Problem. | Peter Auer, Nicol Cesa-Bianchi, Yoav Freund, Robert E. Schapire |
| 1995 | Reductions, Codes, PCPs, and Inapproximability. | Sanjeev Arora |
| 1995 | Sublogarithmic Searching without Multiplications. | Arne Andersson |
| 1995 | Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). | Noga Alon, Jeff Edmonds, Michael Luby |
| 1995 | Improved Algorithms and Analysis for Secretary Problems and Generalizations. | Mikls Ajtai, Nimrod Megiddo, Orli Waarts |
| 1994 | A Lower Bound for the Monotone Depth of Connectivity | Andrew Chi-Chih Yao |
| 1994 | Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time | Karsten Weihe |
| 1994 | On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-in (Extended Abstract) | Gyrgy Turn, Farrokh Vatan |
| 1994 | A note on the Theta number of Lovsz and the generalized Delsarte bound | Mario Szegedy |
| 1994 | Computing with Very Weak Random Sources | Aravind Srinivasan, David Zuckerman |
| 1994 | Expander Codes | Michael Sipser, Daniel A. Spielman |
| 1994 | Efficient Oblivious Branching Programs for Threshold Functions | Rakesh K. Sinha, Jayram S. Thathachar |
| 1994 | On the Power of Quantum Computation | Daniel R. Simon |
| 1994 | Algorithms for Quantum Computation: Discrete Logarithms and Factoring | Peter W. Shor |
| 1994 | Graph Connectivity and Monadic NP | Thomas Schwentick |
| 1994 | On Monotone Formula Closure of SZK | Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung |
| 1994 | On the robustness of functional equations | Ronitt Rubinfeld |
| 1994 | Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract) | R. Ravi |
| 1994 | Nearly Tight Bounds for Wormhole Routing | Abhiram G. Ranade, Saul Schleimer, Daniel Shawcross Wilkerson |
| 1994 | Motion Planning on a Graph (Extended Abstract) | Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki |
| 1994 | On Rank vs. Communication Complexity | Noam Nisan, Avi Wigderson |
| 1994 | Products and Help Bits in Decision Trees | Noam Nisan, Steven Rudich, Michael E. Saks |
| 1994 | An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem | C. Andrew Neff, John H. Reif |
| 1994 | The Load, Capacity and Availability of Quorum Systems | Moni Naor, Avishai Wool |
| 1994 | CS Proofs (Extended Abstracts) | Silvio Micali |