Hacker News Reader

Comment by glitchc | Hacker News Reader

Let's wait for the dust to settle to see if Chen has indeed broken the Shortest Vector Problem for lattices. Bold claims require strong evidence.

View on HN

As pointed out by archgoon (and also pbsd) only for specific parameters is the problem broken, somewhat akin to saying a problem is NP-hard doesnt mean all instances of a problem are hard. But in this case for those parameters it isnt even NP hard.

I was under the impression that the Shortest Vector Problem was NP hard (at least, in some cases). If this works even in those scenarios, that's an even bolder claim by far.

SVP is NP-hard for approximation factors much smaller than this algorithm reaches. This algorithm solves approximation factors of at best O(n^4.5), but NP-hardness is only shown for approximation factors well below n^(1/2). See Figure 1 in page 2 of [1] for a breakdown of the hardness of various approximation factors.

[1] https://cims.nyu.edu/~regev/papers/cvpconp.pdf

Extra-ordinary claims require extra-ordinary evidence!

(my favorite maxim from 2012 era atheism debates on youtube)

But yeah I totally agree. Putting the cart before the horse here with the outlined consequences probably isn't smart, but to be fair, I haven't (and probably couldn't) read the paper.

> (my favorite maxim from 2012 era atheism debates on youtube)

It's a bit older than that: https://en.wikipedia.org/wiki/Extraordinary_claims_require_e...

"Bananas: atheists worst nightmare"?

Chen has not claimed to have broken SVP; only in certain situations. This is a better LLL; not a polynomial hierarchy overturning.

Reply on news.ycombinator.com