| 1998 | Overcoming the Memory Bottleneck in Suffix Tree Construction. | Martin Farach, Paolo Ferragina, S. Muthukrishnan |
| 1998 | Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. | Irit Dinur, Guy Kindler, Shmuel Safra |
| 1998 | On the Single-Source Unsplittable Flow Problem. | Yefim Dinitz, Naveen Garg, Michel X. Goemans |
| 1998 | Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. | Wim van Dam |
| 1998 | Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. | Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg |
| 1998 | The Finite Capacity Dial-A-Ride Problem. | Moses Charikar, Balaji Raghavachari |
| 1998 | Approximating a Finite Metric by a Small Number of Tree Metrics. | Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin |
| 1998 | Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. | Timothy M. Chan |
| 1998 | Towards an Optimal Bit-Reversal Permutation Program. | Larry Carter, Kang Su Gatlin |
| 1998 | Pattern Matching for Spatial Point Sets. | David E. Cardoze, Leonard J. Schulman |
| 1998 | A TDI System and its Application to Approximation Algorithms. | Mao-cheng Cai, Xiaotie Deng, Wenan Zang |
| 1998 | Oblivious Transfer with a Memory-Bounded Receiver. | Christian Cachin, Claude Crpeau, Julien Marcil |
| 1998 | Information Retrieval on the Web. | Andrei Z. Broder, Monika Rauch Henzinger |
| 1998 | Approximation of Diameters: Randomization Doesn't Help. | Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, Lszl Lovsz, Mikls Simonovits |
| 1998 | A Primitive Recursive Algorithm for the General Petri Net Reachability Problem. | Zakaria Bouziane |
| 1998 | Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. | Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen |
| 1998 | On Learning Monotone Boolean Functions. | Avrim Blum, Carl Burch, John Langford |
| 1998 | Bivariate Polynomial Multiplication. | Markus Blser |
| 1998 | Time-Space Tradeoffs for Branching Programs. | Paul Beame, Michael E. Saks, Jayram S. Thathachar |
| 1998 | Quantum Lower Bounds by Polynomials. | Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf |
| 1998 | On the Combinatorial and Topological Complexity of a Single Cell. | Saugata Basu |
| 1998 | The Access Network Design Problem. | Matthew Andrews, Lisa Zhang |
| 1998 | The Quantum Communication Complexity of Sampling. | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
| 1998 | 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. | Andris Ambainis, Rusins Freivalds |
| 1998 | Marked Ancestor Problems. | Stephen Alstrup, Thore Husfeldt, Theis Rauhe |