Mathematics and Efficiency of Song's CVP Hardness Reduction

Song (2026) proves that, for every fixed $0<ε<1$, the closest codeword problem (CCP) for binary linear codes under Hamming distance is NP-hard to approximate within N1-ε, where N is the code length, under deterministic polynomial-time many-one reductions. The code-to-lattice construction gives hardness within N1/2-ε/2 for Euclidean CVP, with the same N aslattice rank. This reaches every fixed Euclidean hardness exponent below one half. Aharonov and Regev (2005), with the constant refined by Gao (2026), place GapCVP at factor cN1/2 in NP for every fixed c>2/(π√3)≈0.3676. NP-hardness at that scale would imply NP=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ₚ(κ-1)+1, where cₚ=max\2,p-1\ and $κ$ is the rank cutoff. Together with ordinary digit products and flexible sampling, this reduces interpolation degrees and output lengths. For CCP gap N1-ε, our explicit schedule gives code length and lattice rank at most n4/ε²+O(1/ε); Song's prescribed binary schedule gives n8/ε²+O(1/ε). Here n counts variables in a common quadratic system, equal to the number of original variables plus clauses for 3SAT. These are dimension bounds, not optimality claims or running-time exponents. The limiting hardness exponents remain Song's.