| 1998 | Cell Flipping in Permutation Diagrams. | Martin Charles Golumbic, Haim Kaplan |
| 1998 | On Uniform DOL Words. | Anna E. Frid |
| 1998 | Nearly Optimal Language Compression Using Extractors. | Lance Fortnow, Sophie Laplante |
| 1998 | Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract). | Joan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, Mahesh Viswanathan |
| 1998 | Axiomatizing the Equational Theory of Regular Tree Languages (Extended Anstract). | Zoltn sik |
| 1998 | On Disguised Double Horn Functions and Extensions. | Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino |
| 1998 | Construction of Non-intersecting Colored Flows Through a Planar Cellular Figure. | Marius Dorkenoo, Marie-Christine Eglin-Leclerc, Eric Rmila |
| 1998 | Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram. | Mohamadou Diallo, Afonso Ferreira, Andrew Rau-Chaplin |
| 1998 | Optimal Broadcasting in Almost Trees and Partial k-trees. | Anders Dessmark, Andrzej Lingas, Hans Olsson, Hiroaki Yamamoto |
| 1998 | The Complexity of Propositional Linear Temporal Logics in Simple Cases (Extended Abstract). | Stphane Demri, Philippe Schnoebelen |
| 1998 | Result-Indistinguishable Zero-Knowledge Proofs: Increased Power and Constant-Round Protocols. | Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung |
| 1998 | Recursively Enumerable Reals and Chaitin Omega Numbers. | Cristian Calude, Peter Hertling, Bakhadyr Khoussainov, Yongge Wang |
| 1998 | On the Structure of Valiant's Complexity Classes. | Peter Brgisser |
| 1998 | A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). | Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss |
| 1998 | Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. | Nader H. Bshouty, Lynn Burroughs |
| 1998 | Simplifying the Modal Mu-Calculus Alternation Hierarchy. | Julian C. Bradfield |
| 1998 | Equivalence Test and Ordering Transformation for Parity-OBDDs of Different Variable Ordering. | Jan Behrens, Stephan Waack |
| 1998 | On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract). | Cristina Bazgan, Miklos Santha, Zsolt Tuza |
| 1998 | Searching Constant Width Mazes Captures the AC | David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum |
| 1998 | The Complexity of Modular Graph Automorphism. | Vikraman Arvind, Richard Beigel, Antoni Lozano |
| 1998 | Bounded Size Dictionary Compression: SC | Sergio De Agostino, Riccardo Silvestri |
| 1997 | Efficient Scaling-Invariant Checking of Timed Bisimulation. | Carsten Weise, Dirk Lenzkes |
| 1997 | On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams. | Stephan Waack |
| 1997 | Unifying Models. | Bernhard Steffen |
| 1997 | Algebraic and Logical Characterizations of Deterministic Linear Time Classes. | Thomas Schwentick |