Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ISAAC M HAIR:
All reports by Author Isaac M Hair:

TR25-153 | 21st October 2025
Isaac M Hair, Amit Sahai

SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\epsilon} n}$

We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for ... more >>>




ISSN 1433-8092 | Imprint