| 1998 | Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). | Luca Trevisan |
| 1998 | Over Words, Two Variables Are as Powerful as One Quantifier Alternation. | Denis Thrien, Thomas Wilke |
| 1998 | On Separating the Read-k-Times Branching Program Hierarchy. | Jayram S. Thathachar |
| 1998 | Almost Optimal Dispersers. | Amnon Ta-Shma |
| 1998 | Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. | Mohammad Amin Shokrollahi, Hal Wasserman |
| 1998 | Approximating Geometrical Graphs via "Spanners" and "Banyans". | Satish Rao, Warren D. Smith |
| 1998 | Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract). | Marcus Peinado, Thomas Lengauer |
| 1998 | A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. | Assaf Natanzon, Ron Shamir, Roded Sharan |
| 1998 | Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations. | Bernard Mourrain, Victor Y. Pan |
| 1998 | Further Algorithmic Aspects of the Local Lemma. | Michael Molloy, Bruce A. Reed |
| 1998 | Analysis of Low Density Codes and Improved Designs Using Irregular Graphs. | Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman |
| 1998 | A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. | Nathan Linial, Alex Samorodnitsky, Avi Wigderson |
| 1998 | Trees and Euclidean Metrics. | Nathan Linial, Avner Magen, Michael E. Saks |
| 1998 | Checking Polynomial Identities over any Field: Towards a Derandomization? | Daniel Lewin, Salil P. Vadhan |
| 1998 | Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. | Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid |
| 1998 | Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. | Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani |
| 1998 | Weak Alternating Automata and Tree Automata Emptiness. | Orna Kupferman, Moshe Y. Vardi |
| 1998 | Segmentation Problems. | Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan |
| 1998 | Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem. | Jon M. Kleinberg |
| 1998 | On Indexed Data Broadcast. | Sanjeev Khanna, Shiyu Zhou |
| 1998 | On Broadcast Disk Paging. | Sanjeev Khanna, Vincenzo Liberatore |
| 1998 | Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching. | David R. Karger, Matthew S. Levine |
| 1998 | Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. | Piotr Indyk, Rajeev Motwani |
| 1998 | Exact Sampling and Approximate Counting Techniques. | Mark Huber |
| 1998 | A Black Box Approach to the Algebraic Set Decomposition Problem. | Ming-Deh A. Huang, Ashwin J. Rao |