| 1998 | Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). | Ran Canetti, Daniele Micciancio, Omer Reingold |
| 1998 | The Random Oracle Methodology, Revisited (Preliminary Version). | Ran Canetti, Oded Goldreich, Shai Halevi |
| 1998 | An Improved Approximation Algorithm for Multiway Cut. | Gruia Calinescu, Howard J. Karloff, Yuval Rabani |
| 1998 | Quantum vs. Classical Communication and Computation. | Harry Buhrman, Richard Cleve, Avi Wigderson |
| 1998 | Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators. | Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook |
| 1998 | A New Composition Theorem for Learning Algorithms. | Nader H. Bshouty |
| 1998 | Min-Wise Independent Permutations (Extended Abstract). | Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher |
| 1998 | Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. | Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala |
| 1998 | The Power of a Pebble: Exploring and Mapping Directed Graphs. | Michael A. Bender, Antonio Fernndez, Dana Ron, Amit Sahai, Salil P. Vadhan |
| 1998 | A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract). | Mihir Bellare, Ran Canetti, Hugo Krawczyk |
| 1998 | One Help Bit Doesn't Help. | Richard Beigel, Tirza Hirst |
| 1998 | NP Might Not Be As Easy As Detecting Unique Solutions. | Richard Beigel, Harry Buhrman, Lance Fortnow |
| 1998 | On the Complexity of Unsatisfiability Proofs for Random | Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks |
| 1998 | On Approximating Arbitrary Metrices by Tree Metrics. | Yair Bartal |
| 1998 | Multicasting in Heterogeneous Networks. | Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber |
| 1998 | The Cost of the Missing Bit: Communication Complexity with Help. | Lszl Babai, Thomas P. Hayes, Peter G. Kimmel |
| 1998 | Approximation Schemes for Euclidean | Sanjeev Arora, Prabhakar Raghavan, Satish Rao |
| 1998 | The Approximability of NP-hard Problems. | Sanjeev Arora |
| 1998 | Stability Results for Networks with Input and Output Blocking. | Matthew Andrews, Lisa Zhang |
| 1998 | Minimizing Stall Time in Single and Parallel Disk Systems. | Susanne Albers, Naveen Garg, Stefano Leonardi |
| 1998 | The Closure of Monadic NP (Extended Abstract). | Mikls Ajtai, Ronald Fagin, Larry J. Stockmeyer |
| 1998 | The Shortest Vector Problem in | Mikls Ajtai |
| 1998 | Adaptive Packet Routing for Bursty Adversarial Traffic. | William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosn |
| 1998 | Quantum Circuits with Mixed States. | Dorit Aharonov, Alexei Y. Kitaev, Noam Nisan |
| 1997 | Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. | Alexander Vardy |