Ethan Mader

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.

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.

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.