2026.08.03 18:27:40 (Mastodon 117032986870147251, Twitter 2084345486102946137) from Daniel J. Bernstein:
Assuming the poly hierarchy doesn't collapse: NP-completeness results for approx-CVP can't cross the wall in 2005 Aharonov-Regev (https://web.archive.org/web/20150905161543/https://cims.nyu.edu/~regev/papers/cvpconp.pdf); FrodoKEM's approx-CVP problem is on the other side of that wall and will never be supported by an NP-completeness theorem.