Mathematics and Efficiency of Song's CVP Hardness Reduction

Shuhong Gao

Submitted by Shuhong Gao

Published November 12, 2026 · Version v1, November 12, 2026 · DOI 10.66977/xsci.2611.001q

Theoretical Computer Science, Algebra, Number Theory

Abstract

\(Song (2026) proves that, for every fixed $0<\epsilon<1$, the closest codeword problem (CCP) for binary linear codes under Hamming distance is NP-hard to
approximate within $N^{1-\epsilon}$, where $N$ is the code length, under deterministic polynomial-time
many-one reductions. The code-to-lattice construction gives hardness within
$N^{1/2-\epsilon/2}$ for Euclidean CVP, with the same $N$ as lattice rank. This reaches every fixed Euclidean hardness exponent below one half. Aharonov--Regev (2005), with the constant refined
by Gao (2026), place GapCVP at factor $cN^{1/2}$ in $\mathrm{NP}\cap\mathrm{coNP}$ for every fixed $c>2/(\pi\sqrt3)\approx0.3676$. NP-hardness at that scale would imply
$\mathrm{NP}=\mathrm{coNP}$.

This paper has two goals: to explain Song's theorem and its mathematics for graduate students, and to make the reduction more efficient. The reduction turns satisfiability into a system of quadratic equations and then into CCP for binary linear codes, and recovers assignments from recurrence relations of algebraic moments. We adapt the method to linear codes over any fixed finite field
of characteristic $p$. A common recurrence for each block column gives a moment window $L=c_p(\kappa-1)+1$, where
$c_p=\max\{2,p-1\}$ and $\kappa$ is the rank cutoff. Together with ordinary digit products and flexible sampling,
this reduces interpolation degrees and output lengths. For CCP gap $N^{1-\epsilon}$, our explicit schedule gives code length and lattice rank at most $n^{4/\epsilon^2+O(1/\epsilon)}$;
Song's prescribed binary schedule gives
$n^{8/\epsilon^2+O(1/\epsilon)}$. Here $n$ counts variables in a common quadratic system, equal to the number of original variables plus clauses for three-literal 3SAT. These are dimension bounds, not
optimality claims or running-time exponents. The limiting hardness exponents remain Song's.\)

View PDF