| 1998 | All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms. | Uri Zwick |
| 1998 | Unsatisfiable Systems of Equations, Over a Finite Field. | Alan R. Woods |
| 1998 | Random Projection: A New Approach to VLSI Layout. | Santosh S. Vempala |
| 1998 | A Randomized Approximation Scheme for Metric MAX-CUT. | Wenceslas Fernandez de la Vega, Claire Kenyon |
| 1998 | A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. | Kasturi R. Varadarajan |
| 1998 | The Complexity of the Approximation of the Bandwidth Problem. | Walter Unger |
| 1998 | The Minimum Equivalent DNF Problem and Shortest Implicants. | Christopher Umans |
| 1998 | Map Graphs in Polynomial Time. | Mikkel Thorup |
| 1998 | Algorithms to Tile the Infinite Grid with Finite Clusters. | Mario Szegedy |
| 1998 | Probabilistically Checkable Proofs with Low Amortized Query Complexity. | Madhu Sudan, Luca Trevisan |
| 1998 | Geometric Separator Theorems & Applications. | Warren D. Smith, Nicholas C. Wormald |
| 1998 | Semidefinite Relaxations for Parallel Machine Scheduling. | Martin Skutella |
| 1998 | Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree. | Graud Snizergues |
| 1998 | Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method. | Arnold Schnhage |
| 1998 | Perfect Information Leader Election in log* | Alexander Russell, David Zuckerman |
| 1998 | Improved Bounds and Algorithms for Hypergraph Two-Coloring. | Jaikumar Radhakrishnan, Aravind Srinivasan |
| 1998 | Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. | Yuval Rabani, Alistair Sinclair, Rolf Wanka |
| 1998 | An Improved Exponential-Time Algorithm for | Ramamohan Paturi, Pavel Pudlk, Michael E. Saks, Francis Zane |
| 1998 | Optimal Time-Space Trade-Offs for Sorting. | Jakob Pagter, Theis Rauhe |
| 1998 | Which Crossing Number is it, Anyway? | Jnos Pach, Gza Tth |
| 1998 | A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices. | Vadim Olshevsky, Victor Y. Pan |
| 1998 | A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. | John C. Mitchell, Mark Mitchell, Andre Scedrov |
| 1998 | The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant. | Daniele Micciancio |
| 1998 | Quantum Cryptography with Imperfect Apparatus. | Dominic Mayers, Andrew Chi-Chih Yao |
| 1998 | Geometric Computation and the Art of Sampling. | Jir Matousek |