Claim PUB-gapcvp-parameter-retuning--thm-main

Exact statement

Theorem 1 (Retuned direct reduction). For every fixed real number $c$ with $0\le c<1/28$ , there is a deterministic polynomial-time mapping that assigns to each $3$ SAT formula $\varphi$ a nonsingular matrix $B\in\mathbb Z^{n\times n}$ , a target $t\in\mathbb Z^n$ , and a radius $r\in\mathbb Q_{>0}$ such that $$\begin{aligned} \varphi\text{ satisfiable} &\implies \operatorname{dist}_2(t,L(B))\le r,\\ \varphi\text{ unsatisfiable} &\implies \operatorname{dist}_2(t,L(B))>n^c r. \end{aligned}$$ Consequently, $\mathsf{GapCVP}^{(2)}_{n^c}$ is NP-hard under deterministic polynomial-time many-one reductions. The same construction gives approximation factor $n^{2c}$ for binary nearest codeword and binary syndrome decoding.