News for hackers. Stuff that matters.
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