5 ms·
I haven't seen too many results that rely on SETH, so just did a bit of research. Ryan Williams (from Stanford) at least doesn't believe SETH is true -- here is
by anonetal 11y ago
I haven't seen too many results that rely on SETH, so just did a bit of research. Ryan Williams (from Stanford) at least doesn't believe SETH is true -- here is a nice talk by him on SETH: http://www.imsc.res.in/~vraman/exact/ryan.pdf http://www.imsc.res.in/~vraman/exact/ryan.pdf
- Sniffnoy 11y agoInteresting to note there slide 5 -- "For many polynomial time problems, improving the best known algorithms, even slightly, implies ¬SETH or ¬ETH." So apparently the edit-distance result discussed here is part of a history of similar results. Edit: More detail on this in slides 11 and forward.