| 1998 | A Note on the Hardness of Tree Isomorphism. Birgit Jenner, Pierre McKenzie, Jacobo Torán |
| 1998 | Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. Jin-Yi Cai, Ajay Nerurkar |
| 1998 | Arthur-Merlin Games in Boolean Decision Trees. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin |
| 1998 | Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. Johannes Köbler, Jochen Messner |
| 1998 | Complexity Issues in Markov Decision Processes. Judy Goldsmith, Martin Mundhenk |
| 1998 | Complexity Limitations on Quantum Computation. Lance Fortnow, John D. Rogers |
| 1998 | Computational Indistinguishability: A Sample Hierarchy. Oded Goldreich, Madhu Sudan |
| 1998 | Hard Sets are Hard to Find. Harry Buhrman, Dieter van Melkebeek |
| 1998 | How to Encode a Logical Structure by an OBDD. Helmut Veith |
| 1998 | Isolation, Matching, and Counting. Eric Allender, Klaus Reinhardt |
| 1998 | Lower Bounds for Computation with Limited Nondeterminism. Hartmut Klauck |
| 1998 | Models of Computation in Coding Theory. Daniel A. Spielman |
| 1998 | Nonrelativizing Separations. Harry Buhrman, Lance Fortnow, Thomas Thierauf |
| 1998 | On Arithmetic Branching Programs. Amos Beimel, Anna Gál |
| 1998 | On Membership Comparable Sets. D. Sivakumar |
| 1998 | On the Resource Bounded Measure of P/poly. Johannes Köbler, Wolfgang Lindner |
| 1998 | Probabilistic Martingales and BPTIME Classes. Kenneth W. Regan, D. Sivakumar |
| 1998 | Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998 |
| 1998 | Proofs of Membership vs. Proofs of Knowledge. Giovanni Di Crescenzo, Russell Impagliazzo |
| 1998 | Randomness is Hard. Harry Buhrman, Leen Torenvliet |
| 1998 | Relationships Between Quantum and Classical Space-Bounded Complexity Classes. John Watrous |
| 1998 | Resource Bounded Measure and Learnability. Wolfgang Lindner, Rainer Schuler, Osamu Watanabe |
| 1998 | Resource-Bounded Measure. Jack H. Lutz |
| 1998 | Solving Intractable Problems with DNA Computing. Richard Beigel, Bin Fu |
| 1998 | The Satisfiability Problem for Probabilistic Ordered Branching Programs. Manindra Agrawal, Thomas Thierauf |
| 1998 | Theory of Periodically Specified Problems: Complexity and Approximability. Madhav V. Marathe, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns |
| 1998 | Two Queries. Harry Buhrman, Lance Fortnow |
| 1998 | Uniformly Hard Languages. Rodney G. Downey, Lance Fortnow |