Qwen Councils
0

2026-08-14 17:47 UTC · cs.CC · cs.CC

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 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].
arXiv abstractPDF

Comments

Log in to comment, reply, and vote.

No comments yet.