| 1998 | Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. | Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup |
| 1998 | A Framework for Fast Quantum Mechanical Algorithms. | Lov K. Grover |
| 1998 | An Exponential Lower Bound for Depth 3 Arithmetic Circuits. | Dima Grigoriev, Marek Karpinski |
| 1998 | Randomized Complexity Lower Bounds. | Dima Grigoriev |
| 1998 | Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. | Oded Goldreich, Amit Sahai, Salil P. Vadhan |
| 1998 | A Sublinear Bipartiteness Tester for Bunded Degree Graphs. | Oded Goldreich, Dana Ron |
| 1998 | On the Limits of Non-Approximability of Lattice Problems. | Oded Goldreich, Shafi Goldwasser |
| 1998 | Protecting Data Privacy in Private Information Retrieval Schemes. | Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin |
| 1998 | A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs. | Anna Gl |
| 1998 | Untitled record | Michael H. Freedman |
| 1998 | Information Theoretic Implications for Pairing Heaps. | Michael L. Fredman |
| 1998 | Robust Efficient Distributed RSA-Key Generation. | Yair Frankel, Philip D. MacKenzie, Moti Yung |
| 1998 | Are Lower Bounds Easier over the Reals? | Herv Fournier, Pascal Koiran |
| 1998 | Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). | Uriel Feige, Christian Scheideler |
| 1998 | Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). | Uriel Feige |
| 1998 | Spot-Checkers. | Funda Ergn, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan |
| 1998 | Concurrent Zero-Knowledge. | Cynthia Dwork, Moni Naor, Amit Sahai |
| 1998 | TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract). | Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott |
| 1998 | Adaptive versus Nonadaptive Attribute-Efficient Learning. | Peter Damaschke |
| 1998 | Non-Interactive and Non-Malleable Commitment. | Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky |
| 1998 | On the Complexity of Protein Folding (Extended Abstract). | Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis |
| 1998 | Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks. | Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andra W. Richa, Klaus Schrder, Ramesh K. Sitaraman, Berthold Vcking |
| 1998 | Planar Map Graphs. | Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou |
| 1998 | Algorithms for Capacitated Vehicle Routing. | Moses Charikar, Samir Khuller, Balaji Raghavachari |
| 1998 | Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and | Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha |