Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2

Isaac M Hair, Amit Sahai

For every constant $2<p<\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the ${\ell }_p$-shortest vector problem for lattices of…