Post

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

0 reposts1 like

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…
Rob Patro
@robp.bsky.social

I thought that ETH false does not necessarily imply that SETH is false, despite that the latter is stronger. Do the OpenAI (and Anthropic) results imply SETH is false as well?