Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric

At the heart of our construction is a new combinatorial object we call a misaligner, which allows us to carefully align edit distances with Hamming distances. I will also discuss how our framework could potentially be extended to achieve even higher rates—possibly up to 1/5—given sufficient computational resources.

Beyond the embedding itself, I will outline several algorithmic implications of our result. In particular, our embedding yields improved conditional lower bounds for fundamental problems in the edit metric, including the closest pair and discrete 1-center problems. It also strengthens hardness-of-approximation results for edit-distance-based clustering and the Steiner tree problem, now with optimal dependence on the dimension.

Finally, I will present a nearly matching upper bound: we prove that no isometric embedding from Hamming to edit distance can have rate exceeding $3/7 + o(1)$. To prove this, we uncover structural properties that any such embedding must satisfy—revealing inherent limitations that any approach to high-rate isometric embedding must contend with.