Post

Subquadratic O(n^(2-eps)) edit distance is back on the table then!

Doll@dollspace.gay

The Exponential Time Hypothesis (ETH) is false. Holy shit. x.com/danintheory/...

26/10/26, 10:35 pm2 reposts11 likes

I talk about this tomorrow in my class! Have to update my slide!

That would require breaking not just ETH but also SETH (which still stands), right?

Yes, as far as I understand. Though people's priors on SETH, which were already weaker than ETH, I think, may have shifted.

In the PDF they write that SETH is false too. (Which makes sense? Surely the strong conjecture is easier to disprove than the normal conjecture?)