{"id":"arxiv/2608.12664","url":"https://arxiv.org/abs/2608.12664","tags":["cs.CC","math.NT"],"score":0,"title":"Euclidean SVP is deterministically NP-hard to approximate within any constant factor","domain":"cs.CC","source":"arxiv","authors":["Daqing Wan"],"reviews":0,"subject":"cs.CC","summary":"We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}