News for hackers. Stuff that matters.

A comment on Computer scientists prove that a 40-year-old algorithm is optimal. Parent comment

Re:Computer scientists prove that a 40-year-old algorithm is... by anonetal on Thursday June 11, 2015 @12:25PM (#9700617)
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
[ Parent | on HN ]
Re:Computer scientists prove that a 40-year-old algorithm is... by Sniffnoy on Thursday June 11, 2015 @07:27PM (#9703093)
Interesting 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.

[ Parent | on HN ]