| 1998 | Jitter Control in QoS Networks. | Yishay Mansour, Boaz Patt-Shamir |
| 1998 | A Characterization of NC by Tree Recurrence. | Daniel Leivant |
| 1998 | Recommendation Systems: A Probabilistic Analysis. | Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins |
| 1998 | Lower Bounds for Zero Knowledge on the Internet. | Joe Kilian, Erez Petrank, Charles Rackoff |
| 1998 | Theoretical Issues in Probabilistic Artificial Intelligence. | Michael J. Kearns |
| 1998 | Local Search in Smooth Convex Sets. | Ravi Kannan, Andreas Nolte |
| 1998 | Orchestrating Quartets: Approximation and Data Correction. | Tao Jiang, Paul E. Kearney, Ming Li |
| 1998 | Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. | Kamal Jain |
| 1998 | Faster Algorithms for String Matching Problems: Matching the Convolution Bound. | Piotr Indyk |
| 1998 | On Approximate Nearest Neighbors in Non-Euclidean Spaces. | Piotr Indyk |
| 1998 | Randomness vs. Time: De-Randomization under a Uniform Assumption. | Russell Impagliazzo, Avi Wigderson |
| 1998 | Which Problems Have Strongly Exponential Complexity? | Russell Impagliazzo, Ramamohan Paturi, Francis Zane |
| 1998 | The Security of Individual RSA Bits. | Johan Hstad, Mats Nslund |
| 1998 | Satisfiability of Word Equations with Constants is in Exponential Space. | Claudio Gutierrez |
| 1998 | Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. | Venkatesan Guruswami, Madhu Sudan |
| 1998 | A Tight Characterization of NP with 3 Query PCPs. | Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan |
| 1998 | Lower Bounds for (MOD p - MOD m) Circuits. | Vince Grolmusz, Gbor Tardos |
| 1998 | Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. | Dima Grigoriev, Alexander A. Razborov |
| 1998 | Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. | Dima Grigoriev |
| 1998 | The Complexity of Acyclic Conjunctive Queries. | Georg Gottlob, Nicola Leone, Francesco Scarcello |
| 1998 | Testing Monotonicity. | Oded Goldreich, Shafi Goldwasser, Eric P. Lehman, Dana Ron |
| 1998 | Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. | Naveen Garg, Jochen Knemann |
| 1998 | Stability of Adversarial Queues via Fluid Models. | David Gamarnik |
| 1998 | Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. | Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1998 | Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. | Uriel Feige, Joe Kilian |