Re:A quick post on Chen's algorithm
by glitchc on Tuesday April 16, 2024 @05:48PM
(#40057641)
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.
[ Parent
| on HN ]
Re:A quick post on Chen's algorithm
by gradschoolfail on Tuesday April 16, 2024 @07:36PM
(#40058695)
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.
Re:A quick post on Chen's algorithm
by stoniejohnson on Tuesday April 16, 2024 @05:59PM
(#40057738)
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.
Re:A quick post on Chen's algorithm
by deathanatos on Tuesday April 16, 2024 @07:33PM
(#40058666)
> (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"?