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

There are no comments on this comment yet.