Research

A Strongly Subquadratic (3+ε)-Approximation for Weighted Edit Distance over Arbitrary Metrics

Ethan Mader, Borna Tavasoli, Jihan Wang

A randomized \((3+\varepsilon)\)-approximation algorithm for weighted edit distance over arbitrary metrics running in \(\tilde{O}_{\varepsilon}\mkern-2mu\left(n^{7/4}\right)\) time, the first constant-factor approximation for the problem in strongly subquadratic time.

September 2026[arXiv]

A Faster 3-Approximation for Sublinear Edit Distances

Emily Fox, Ethan Mader, Kent Quanrud, Borna Tavasoli, Jihan Wang

A randomized \((3+\varepsilon)\)-approximation algorithm for edit distance running in \(\tilde{O}_{\varepsilon}\mkern-2mu\left(n^{6/5}\mathrm{OPT}^{2/5}\right)\) time, improving on a prior \(\tilde{O}_{\varepsilon}\mkern-2mu\left(n^{8/5+o(1)}\right)\) time algorithm when the edit distance is sublinear.

June 2026[Manuscript]

Kolmogorov Complexity of Graph Classes

Ethan Mader, Zachary Lee

Upper bounds on the Kolmogorov complexity of graph classes in terms of structural parameters such as clique-width, separation number, and closure under graph products.

CS 584: Complexity Theory · Spring 2025[Slides]

Semidefinite Programming and Approximate Pure Nash Equilibria for Cut Games

Ethan Mader

A study of the SDP-based algorithm of Caragiannis and Jiang for \(\rho\)-approximate pure Nash equilibria in cut games, testing whether alternative rounding functions can improve their 2.7371 factor.

CS 593AE: Algorithmic Economics · Fall 2024[Slides]

CS 381: Analysis of Algorithms

Teaching Assistant · Purdue University · Spring 2026, Fall 2026

[Fall 2026 PSO problem sets]