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

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

23h

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

23h

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

21h

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…

Jarno N. Alanko

@jnalanko.bsky.social

21h

Actually, I'm told that this result is still ok: it's actually based on the orthogonal vectors hypothesis, which can be true even if ETH is false.

Ragnar {Groot Koerkamp}

@curiouscoding.nl

Let's see if that falls next. At this point nothing surprises me anymore... (I should read up on how exponential time ETH things relate to poly time OV actually.)

27/10/26, 10:27 am0 reposts0 likes

No replies yet.