Metraipolis › archive › dc_c7d4defd004b
Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2 — arXiv:2608.14529
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.14529
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T04:08:38.011Z
- SHA-256 of the archived text
e42a4b3054eb2a986b50d15634d0329375e05cf563fb62edb703ae33057e80d9- Stable URL of this page
https://metraipolis.com/documento/dc_c7d4defd004b
How to cite
Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2 — arXiv:2608.14529 — arXiv (en), https://arxiv.org/abs/2608.14529 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c7d4defd004b (Metraipolis archive dc_c7d4defd004b, sha256 e42a4b3054eb2a986b50d15634d0329375e05cf563fb62edb703ae33057e80d9)
BibTeX
@misc{dcc7d4defd004b,
title = {Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2 — arXiv:2608.14529},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.14529},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c7d4defd004b; sha256 e42a4b3054eb2a986b50d15634d0329375e05cf563fb62edb703ae33057e80d9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.14529. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 rank $M$ is NP hard to approximate within a factor of $M^\varepsilon$, via a deterministic reduction. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. The reduction builds on the polynomial-gap CVP construction of OpenAI [OpenAI 2026] and the direct reduction to SVP for $p>2$ of Hair and Sahai [STOC'26].
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-17 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.14529 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T03:59:38.750Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).