Edit distance: a (1+ε)-approximation in truly subquadratic time n^(2−δ)

Constant-factor approximation is possible in truly subquadratic time (Chakraborty, Das, Goldenberg, Koucký and Saks, arXiv:1810.03664, FOCS 2018, Õ(n^{2−2/7})) and even in near-linear time n^{1+ε} with a constant depending on ε (Andoni–Nosatzki, arXiv:2005.07678, FOCS 2020), after earlier (log n)^{O(1/ε)} approximation in n^{1+ε} time (Andoni–Krauthgamer–Onak 2010) and the large-distance case (Brakensiek–Rubinstein, arXiv:1904.05390). For small constants, (3+ε)-approximations run in truly subquadratic time (Andoni 2018; Goldenberg–Rubinstein–Saha 2020, about n^{1.6}), and Gorbachev (arXiv:2610.01311, 1 October 2026, unrefereed preprint) gives a randomized factor-exactly-3 approximation in Õ(N^{11/6}) time (Õ(N^{40/21}) for arbitrary metric edit weights). In these algorithms the factor 3 comes from routing comparisons through shared 'center' strings by the triangle inequality, ed(U,Y[p..q)) ≤ r + ed(C,Y[p..q)) ≤ ed(U,Y[p..q)) + 2r, and the +ε from sample-based search; Gorbachev pays for the vanishing excess by moving each center one edit closer to its block (handled with implicit DIST matrices), at the price of a slower exponent than the N^{1.6+o(1)} of Goldenberg–Rubinstein–Saha. He states that a (3−δ)-approximation in truly subquadratic time would need new ideas, that (1+ε) in truly subquadratic time is open, and that no known fine-grained lower bound even excludes (1+ε) in O(N) time. He also proves that the metric assumption is necessary: for non-metric weights, any approximation needs Ω(N²) oracle queries, and is OV-hard over constant alphabets. On the (1+ε) side, Mao and Rubinstein (arXiv:2603.29702, accepted to STOC 2026) give randomized (1+ε)-approximation for edit distance (and (1−ε) for LCS) in time n²/2^{log^{Ω(1)} n}, a super-polylogarithmic but not polynomial saving, which separates approximate from exact edit distance (the latter cannot be sped up beyond polylogarithmic factors under the hypotheses of Abboud–Hansen–Vassilevska Williams–Williams). Haeupler, Rubinstein and Shahrasbi (arXiv:1810.11863) obtain (1+ε) in near-linear time only for strings with an indexing structure. Whether (1+ε) is achievable in n^{2−δ} time for general strings is open.

Edit distance underlies sequence alignment in genomics, spelling and plagiarism detection and version control; a (1+ε) subquadratic algorithm would speed these pipelines at a 1% error level on long sequences, and a hardness result would justify heuristics.

Either a randomized or deterministic algorithm with (1+ε)-approximation in time O(n^{2−δ}) for every fixed ε>0, or a proof (conditional on a standard hypothesis such as SETH or a fine-grained hypothesis) that for some ε>0 no such algorithm exists.