Daniel J. Bernstein on Nostr: Assuming the poly hierarchy doesn't collapse: NP-completeness results for approx-CVP ...
Published at
2026-08-03 18:27:40 UTCEvent JSON
{
"id": "3d08963d1ba668b9b62440be84827cc24912223794e8bf6b5799eb39599a197e",
"pubkey": "dfc7d34aef2cd15aa9eb1c20d755dbf8cafb7bbd155f737c941e14d8c3c1f95a",
"created_at": 1785781660,
"kind": 1,
"tags": [
[
"proxy",
"https://mastodon.cr.yp.to/users/djb/statuses/117032986870147251",
"activitypub"
],
[
"client",
"Mostr",
"31990:6be38f8c63df7dbf84db7ec4a6e6fbbd8d19dca3b980efad18585c46f04b26f9:mostr",
"wss://relay.ditto.pub"
]
],
"content": "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.",
"sig": "6bba52843c29e58934d0a33c4a419b1bc998b85bd24ed68b3ac57b4f71cafaba93fb04f7afd4273c8ba7371998b9aaefbf0156f8c74e09d00df1d841e2b78e75"
}
