| 1998 | A Black Box Approach to the Algebraic Set Decomposition Problem. Ming-Deh A. Huang, Ashwin J. Rao |
| 1998 | A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs. Anna Gál |
| 1998 | A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Nathan Linial, Alex Samorodnitsky, Avi Wigderson |
| 1998 | A Framework for Fast Quantum Mechanical Algorithms. Lov K. Grover |
| 1998 | A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract). Mihir Bellare, Ran Canetti, Hugo Krawczyk |
| 1998 | A New Composition Theorem for Learning Algorithms. Nader H. Bshouty |
| 1998 | A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. Assaf Natanzon, Ron Shamir, Roded Sharan |
| 1998 | A Sublinear Bipartiteness Tester for Bunded Degree Graphs. Oded Goldreich, Dana Ron |
| 1998 | Adaptive Packet Routing for Bursty Adversarial Traffic. William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén |
| 1998 | Adaptive versus Nonadaptive Attribute-Efficient Learning. Peter Damaschke |
| 1998 | Algorithms for Capacitated Vehicle Routing. Moses Charikar, Samir Khuller, Balaji Raghavachari |
| 1998 | Almost Optimal Dispersers. Amnon Ta-Shma |
| 1998 | An Exponential Lower Bound for Depth 3 Arithmetic Circuits. Dima Grigoriev, Marek Karpinski |
| 1998 | An Improved Approximation Algorithm for Multiway Cut. Gruia Calinescu, Howard J. Karloff, Yuval Rabani |
| 1998 | Analysis of Low Density Codes and Improved Designs Using Irregular Graphs. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman |
| 1998 | Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Piotr Indyk, Rajeev Motwani |
| 1998 | Approximating Geometrical Graphs via "Spanners" and "Banyans". Satish Rao, Warren D. Smith |
| 1998 | Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). Uriel Feige |
| 1998 | Approximation Schemes for Euclidean Sanjeev Arora, Prabhakar Raghavan, Satish Rao |
| 1998 | Are Lower Bounds Easier over the Reals? Hervé Fournier, Pascal Koiran |
| 1998 | Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations. Bernard Mourrain, Victor Y. Pan |
| 1998 | Checking Polynomial Identities over any Field: Towards a Derandomization? Daniel Lewin, Salil P. Vadhan |
| 1998 | Computing Local Dimension of a Semialgebraic Set. Nicolai N. Vorobjov Jr. |
| 1998 | Concurrent Zero-Knowledge. Cynthia Dwork, Moni Naor, Amit Sahai |
| 1998 | Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem. Jon M. Kleinberg |
| 1998 | Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. Mohammad Amin Shokrollahi, Hal Wasserman |
| 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 | Exact Sampling and Approximate Counting Techniques. Mark Huber |
| 1998 | Finding Almost-Satisfying Assignments. Uri Zwick |
| 1998 | Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching. David R. Karger, Matthew S. Levine |
| 1998 | Further Algorithmic Aspects of the Local Lemma. Michael Molloy, Bruce A. Reed |
| 1998 | Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. Oded Goldreich, Amit Sahai, Salil P. Vadhan |
| 1998 | Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). Uriel Feige, Christian Scheideler |
| 1998 | Information Theoretic Implications for Pairing Heaps. Michael L. Fredman |
| 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 | Min-Wise Independent Permutations (Extended Abstract). Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher |
| 1998 | Minimizing Stall Time in Single and Parallel Disk Systems. Susanne Albers, Naveen Garg, Stefano Leonardi |
| 1998 | Multicasting in Heterogeneous Networks. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber |
| 1998 | NP Might Not Be As Easy As Detecting Unique Solutions. Richard Beigel, Harry Buhrman, Lance Fortnow |
| 1998 | Non-Interactive and Non-Malleable Commitment. Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky |
| 1998 | On Approximating Arbitrary Metrices by Tree Metrics. Yair Bartal |
| 1998 | On Broadcast Disk Paging. Sanjeev Khanna, Vincenzo Liberatore |
| 1998 | On Indexed Data Broadcast. Sanjeev Khanna, Shiyu Zhou |
| 1998 | On Separating the Read-k-Times Branching Program Hierarchy. Jayram S. Thathachar |
| 1998 | On the Complexity of Protein Folding (Extended Abstract). Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1998 | On the Complexity of Unsatisfiability Proofs for Random Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks |
| 1998 | On the Limits of Non-Approximability of Lattice Problems. Oded Goldreich, Shafi Goldwasser |
| 1998 | One Help Bit Doesn't Help. Richard Beigel, Tirza Hirst |
| 1998 | Over Words, Two Variables Are as Powerful as One Quantifier Alternation. Denis Thérien, Thomas Wilke |
| 1998 | Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). Ran Canetti, Daniele Micciancio, Omer Reingold |
| 1998 | Planar Map Graphs. Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou |
| 1998 | Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup |
| 1998 | Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998 Jeffrey Scott Vitter |
| 1998 | Protecting Data Privacy in Private Information Retrieval Schemes. Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin |
| 1998 | Quantum Circuits with Mixed States. Dorit Aharonov, Alexei Y. Kitaev, Noam Nisan |
| 1998 | Quantum vs. Classical Communication and Computation. Harry Buhrman, Richard Cleve, Avi Wigderson |
| 1998 | Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract). Marcus Peinado, Thomas Lengauer |
| 1998 | Randomized Complexity Lower Bounds. Dima Grigoriev |
| 1998 | Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks. Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, Ramesh K. Sitaraman, Berthold Vöcking |
| 1998 | Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). Luca Trevisan |
| 1998 | Robust Efficient Distributed RSA-Key Generation. Yair Frankel, Philip D. MacKenzie, Moti Yung |
| 1998 | Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha |
| 1998 | Segmentation Problems. Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan |
| 1998 | Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala |
| 1998 | Spot-Checkers. Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan |
| 1998 | Stability Results for Networks with Input and Output Blocking. Matthew Andrews, Lisa Zhang |
| 1998 | TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract). Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott |
| 1998 | The Approximability of NP-hard Problems. Sanjeev Arora |
| 1998 | The Closure of Monadic NP (Extended Abstract). Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer |
| 1998 | The Cost of the Missing Bit: Communication Complexity with Help. László Babai, Thomas P. Hayes, Peter G. Kimmel |
| 1998 | The Power of a Pebble: Exploring and Mapping Directed Graphs. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan |
| 1998 | The Random Oracle Methodology, Revisited (Preliminary Version). Ran Canetti, Oded Goldreich, Shai Halevi |
| 1998 | The Shortest Vector Problem in Miklós Ajtai |
| 1998 | Trees and Euclidean Metrics. Nathan Linial, Avner Magen, Michael E. Saks |
| 1998 | Weak Alternating Automata and Tree Automata Emptiness. Orna Kupferman, Moshe Y. Vardi |