News for hackers. Stuff that matters.
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.
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.
Re:A quick post on Chen's algorithm by vitus on Tuesday April 16, 2024 @06:14PM (#40057923)
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.
Re:A quick post on Chen's algorithm by pbsd on Tuesday April 16, 2024 @07:10PM (#40058449)
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

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...

Re:A quick post on Chen's algorithm by ecosystem on Wednesday April 17, 2024 @02:08AM (#40061035)
"Bananas: atheists worst nightmare"?
Re:A quick post on Chen's algorithm by archgoon on Tuesday April 16, 2024 @06:33PM (#40058116)
Chen has not claimed to have broken SVP; only in certain situations. This is a better LLL; not a polynomial hierarchy overturning.