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/...

x.comDan Roberts (@danintheory) on XWe are announcing three new discoveries in mathematics, computer science, and physics about harmonic analysis, complexity theory, and quantum field theory. https://t.co/9BX8HWQDTJ

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

Rob Patro

@robp.bsky.social

16h

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

Jarno N. Alanko

@jnalanko.bsky.social

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

Rob Patro

@robp.bsky.social

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

Ragnar {Groot Koerkamp}

@curiouscoding.nl

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?)

Jarno N. Alanko

@jnalanko.bsky.social

You right... SETH implies ETH, so (not ETH) implies (not SETH). Amazing! So this also breaks a lower bound from the Helsinki lab where they showed that indexing graphs for pattern matching requires quadratic time: www.sciencedirect.com/science/arti....

sciencedirect.comGraphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH failsThe string matching problem on a node-labeled graph G=(V,E) asks whether a given pattern string P equals the concatenation of node labels of some path…