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...