3 ms·

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.

stoniejohnson 3y ago
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.
- deathanatos 3y ago
  > (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_extraordinary_evidence https://en.wikipedia.org/wiki/Extraordinary_claims_require_e...
- ecosystem 3y ago
  "Bananas: atheists worst nightmare"?
vitus 3y ago
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.
- pbsd 3y ago
  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 https://cims.nyu.edu/~regev/papers/cvpconp.pdf
archgoon 3y ago
Chen has not claimed to have broken SVP; only in certain situations. This is a better LLL; not a polynomial hierarchy overturning.
gradschoolfail 3y ago
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.

3 ms·

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.

by glitchc 3y ago

stoniejohnson 3y ago
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.
- deathanatos 3y ago
  > (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_extraordinary_evidence https://en.wikipedia.org/wiki/Extraordinary_claims_require_e...
- ecosystem 3y ago
  "Bananas: atheists worst nightmare"?
vitus 3y ago
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.
- pbsd 3y ago
  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 https://cims.nyu.edu/~regev/papers/cvpconp.pdf
archgoon 3y ago
Chen has not claimed to have broken SVP; only in certain situations. This is a better LLL; not a polynomial hierarchy overturning.
gradschoolfail 3y ago
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.