| 1998 | 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. Andris Ambainis, Rusins Freivalds |
| 1998 | 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998 |
| 1998 | A Characterization of NC by Tree Recurrence. Daniel Leivant |
| 1998 | A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. Kasturi R. Varadarajan |
| 1998 | A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. John C. Mitchell, Mark Mitchell, Andre Scedrov |
| 1998 | A Primitive Recursive Algorithm for the General Petri Net Reachability Problem. Zakaria Bouziane |
| 1998 | A Randomized Approximation Scheme for Metric MAX-CUT. Wenceslas Fernandez de la Vega, Claire Kenyon |
| 1998 | A TDI System and its Application to Approximation Algorithms. Mao-cheng Cai, Xiaotie Deng, Wenan Zang |
| 1998 | A Tight Characterization of NP with 3 Query PCPs. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan |
| 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 | Algorithms to Tile the Infinite Grid with Finite Clusters. Mario Szegedy |
| 1998 | All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms. Uri Zwick |
| 1998 | An Improved Exponential-Time Algorithm for Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane |
| 1998 | Approximating a Finite Metric by a Small Number of Tree Metrics. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin |
| 1998 | Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. Irit Dinur, Guy Kindler, Shmuel Safra |
| 1998 | Approximation of Diameters: Randomization Doesn't Help. Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits |
| 1998 | Bivariate Polynomial Multiplication. Markus Bläser |
| 1998 | Concurrent Reachability Games. Luca de Alfaro, Thomas A. Henzinger, Orna Kupferman |
| 1998 | Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree. Géraud Sénizergues |
| 1998 | Delayed Information and Action in On-line Algorithms. Susanne Albers, Moses Charikar, Michael Mitzenmacher |
| 1998 | Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg |
| 1998 | Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. Dima Grigoriev, Alexander A. Razborov |
| 1998 | Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen |
| 1998 | Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Kamal Jain |
| 1998 | Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. Alan M. Frieze, Ravi Kannan, Santosh S. Vempala |
| 1998 | Faster Algorithms for String Matching Problems: Matching the Convolution Bound. Piotr Indyk |
| 1998 | Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. Naveen Garg, Jochen Könemann |
| 1998 | Geometric Computation and the Art of Sampling. Jirí Matousek |
| 1998 | Geometric Separator Theorems & Applications. Warren D. Smith, Nicholas C. Wormald |
| 1998 | Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. Uriel Feige, Joe Kilian |
| 1998 | Improved Bounds and Algorithms for Hypergraph Two-Coloring. Jaikumar Radhakrishnan, Aravind Srinivasan |
| 1998 | Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. Venkatesan Guruswami, Madhu Sudan |
| 1998 | Information Retrieval on the Web. Andrei Z. Broder, Monika Rauch Henzinger |
| 1998 | Jitter Control in QoS Networks. Yishay Mansour, Boaz Patt-Shamir |
| 1998 | Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. Yuval Rabani, Alistair Sinclair, Rolf Wanka |
| 1998 | Local Search in Smooth Convex Sets. Ravi Kannan, Andreas Nolte |
| 1998 | Lower Bounds for (MOD p - MOD m) Circuits. Vince Grolmusz, Gábor Tardos |
| 1998 | Lower Bounds for Zero Knowledge on the Internet. Joe Kilian, Erez Petrank, Charles Rackoff |
| 1998 | Map Graphs in Polynomial Time. Mikkel Thorup |
| 1998 | Marked Ancestor Problems. Stephen Alstrup, Thore Husfeldt, Theis Rauhe |
| 1998 | Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method. Arnold Schönhage |
| 1998 | Oblivious Transfer with a Memory-Bounded Receiver. Christian Cachin, Claude Crépeau, Julien Marcil |
| 1998 | On Approximate Nearest Neighbors in Non-Euclidean Spaces. Piotr Indyk |
| 1998 | On Learning Monotone Boolean Functions. Avrim Blum, Carl Burch, John Langford |
| 1998 | On the Combinatorial and Topological Complexity of a Single Cell. Saugata Basu |
| 1998 | On the Single-Source Unsplittable Flow Problem. Yefim Dinitz, Naveen Garg, Michel X. Goemans |
| 1998 | Optimal Time-Space Trade-Offs for Sorting. Jakob Pagter, Theis Rauhe |
| 1998 | Orchestrating Quartets: Approximation and Data Correction. Tao Jiang, Paul E. Kearney, Ming Li |
| 1998 | Overcoming the Memory Bottleneck in Suffix Tree Construction. Martin Farach, Paolo Ferragina, S. Muthukrishnan |
| 1998 | Parametric and Kinetic Minimum Spanning Trees. Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, Monika Rauch Henzinger |
| 1998 | Pattern Matching for Spatial Point Sets. David E. Cardoze, Leonard J. Schulman |
| 1998 | Perfect Information Leader Election in log* Alexander Russell, David Zuckerman |
| 1998 | Probabilistically Checkable Proofs with Low Amortized Query Complexity. Madhu Sudan, Luca Trevisan |
| 1998 | Protocols for Asymmetric Communication Channels. Micah Adler, Bruce M. Maggs |
| 1998 | Quantum Cryptography with Imperfect Apparatus. Dominic Mayers, Andrew Chi-Chih Yao |
| 1998 | Quantum Lower Bounds by Polynomials. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf |
| 1998 | Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. Wim van Dam |
| 1998 | Random Projection: A New Approach to VLSI Layout. Santosh S. Vempala |
| 1998 | Randomness vs. Time: De-Randomization under a Uniform Assumption. Russell Impagliazzo, Avi Wigderson |
| 1998 | Recommendation Systems: A Probabilistic Analysis. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins |
| 1998 | Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. Timothy M. Chan |
| 1998 | Satisfiability of Word Equations with Constants is in Exponential Space. Claudio Gutierrez |
| 1998 | Semidefinite Relaxations for Parallel Machine Scheduling. Martin Skutella |
| 1998 | Stability of Adversarial Queues via Fluid Models. David Gamarnik |
| 1998 | Testing Monotonicity. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron |
| 1998 | The Access Network Design Problem. Matthew Andrews, Lisa Zhang |
| 1998 | The Complexity of Acyclic Conjunctive Queries. Georg Gottlob, Nicola Leone, Francesco Scarcello |
| 1998 | The Complexity of the Approximation of the Bandwidth Problem. Walter Unger |
| 1998 | The Finite Capacity Dial-A-Ride Problem. Moses Charikar, Balaji Raghavachari |
| 1998 | The Minimum Equivalent DNF Problem and Shortest Implicants. Christopher Umans |
| 1998 | The Quantum Communication Complexity of Sampling. Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
| 1998 | The Security of Individual RSA Bits. Johan Håstad, Mats Näslund |
| 1998 | The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant. Daniele Micciancio |
| 1998 | Theoretical Issues in Probabilistic Artificial Intelligence. Michael J. Kearns |
| 1998 | Time-Space Tradeoffs for Branching Programs. Paul Beame, Michael E. Saks, Jayram S. Thathachar |
| 1998 | Towards an Optimal Bit-Reversal Permutation Program. Larry Carter, Kang Su Gatlin |
| 1998 | Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. Dima Grigoriev |
| 1998 | Unsatisfiable Systems of Equations, Over a Finite Field. Alan R. Woods |
| 1998 | Which Crossing Number is it, Anyway? János Pach, Géza Tóth |
| 1998 | Which Problems Have Strongly Exponential Complexity? Russell Impagliazzo, Ramamohan Paturi, Francis Zane |