Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2
For every constant $2<p<\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we give a deterministic polynomial-time reduction from 3SAT to $M^\varepsilon$-GapSVP$_p$, where $M$ is the lattice rank. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. The reduction builds on the polynomial-gap CVP construction of OpenAI and the direct reduction to SVP for $p>2$ of Hair and Sahai [STOC'26].
Comments
Log in to comment, reply, and vote.
No comments yet.