In the nearest codeword problem (NCP) one is given a linear code over a finite field and a target word , and must find a codeword closest to in Hamming distance. In the closest vector problem (CVP) one is given a full-rank lattice and a target , and must find a lattice point closest to in an norm. Both problems are NP-hard to solve exactly, so the question is the approximation factor that efficient algorithms can reach.
In coding theory and in lattice-based cryptography the code or lattice is usually fixed long in advance, and only the target changes. This motivates the preprocessing model [FM04]: an algorithm may first spend unbounded time on the code or lattice alone and store a polynomial-length advice string; afterwards it receives targets and must answer each in polynomial time. With preprocessing, NCP over a fixed field is approximable within [APY10], and the gap version of CVP within in [AR05] and in for [Peikert08].
Timeline of hardness results:
Fix a finite field . A fixed code with targets for instances consists of a finite coordinate set of size , a linear subspace , and a target for every instance. The distance is the least Hamming distance from to a codeword.
Fix a norm exponent and set (so for ). A fixed lattice with targets consists of a -submodule that contains for some integer (hence has full rank), and an integer target for every instance. The distance is the infimum of over ; it is attained.
Instances are 3SAT formulas on variables, written as bit strings with : one bit for each of the ordered triples of literals, recording whether that clause is present. is the set of satisfiable instances.
The point of the preprocessing model is visible in the order of quantifiers: the code or lattice depends only on , and only the target depends on the instance .
For every finite field and every there is a constant such that for every there are a fixed code with , targets and an integer radius with
For every and every there is a constant such that for every there are a fixed full-rank lattice with , integer targets and an integer radius with
In the goal, , , and are the objects that the paper constructs, not arbitrary ones. is the code of the fixed linear system of Construction 4.5 for the 3SAT verifier, extended to , and is the target of Lemma 3.11. , its targets and its radius are those of Lemma 3.12 for the same system. The instance enters only through the right-hand side .
The milestones follow the paper's proof: the verifier and its quadratic equations (Definitions 3.13–3.14, Claim 3.15, the 3SAT circuit); the fixed-verifier linear system and its gap (Theorem 4.6); the explicit moment representations of Appendix A (Theorems A.7 and A.8); the size and gap bound (Theorem 4.8); the conversion to lattices (Lemma 3.12); the test of search outputs (Lemma 5.2); and Theorem 5.1 for an arbitrary quadratic verifier, from which the 3SAT form follows.
Each step that the paper proves by a construction has a milestone for the object it constructs: Theorem 4.8 for the fixed linear system of Construction 4.5, Lemma 3.12 for the Construction A lattice and its Walsh–Hadamard transform, and Theorem 5.1 for the resulting code and lattice. The milestones marked "existence form" assert only that some object with the stated properties exists.
Section 6 of the paper gives a second reduction, which does not use the moment method and is not needed for the goal. It starts from a PCP that is query-oblivious with enumerable predicate families: the query locations and the family of possible acceptance predicates depend only on the random string , not on the instance (Definition 6.1). The variables are the accepting views of the verifier, and an injective linear map encodes, for every proof location and every symbol , the variables of the views that answer at (Construction 6.2).
Let the PCP have alphabet , random bits, queries, perfect completeness and soundness error for a language , let the code have relative distance , and let be an integer. Then the resulting fixed code and targets satisfy, with ,
and the block length is .
Five milestones cover this theorem: the bound on the number of accepting views, the inequality (31) behind the soundness proof, completeness, soundness, and the full statement.
Theorem 5.1 is the combinatorial heart of the paper's main result: unless , no preprocessing algorithm with polynomial advice and polynomial online time approximates NCP within or CVP in within . These are the first polynomial hardness factors in the preprocessing model, and for NCP and the gap version of CVP they nearly match the best preprocessing algorithms. Hardness with preprocessing is the relevant notion for decoding problems in which the code or lattice is a public parameter.
Theorem 6.4 reduces languages with query-oblivious PCPs to NCP with preprocessing without the smoothness assumption of [KPV14]. With known PCPs the paper derives from it hardness within , unless has circuits of size (Corollary 6.6), a factor that is weaker than the main bounds but already larger than that of [KPV14].
The result is proved in an unrefereed manuscript (a STOC 2027 submission). Its proof combines a moment-based encoding of verifier computations, explicit evaluation tables over finite-field towers, a Hankel-matrix reconstruction argument and code-to-lattice conversions; each of these steps is checked here. A complete Lean 4 / Mathlib proof of every statement in this mission exists and is uploaded with it; the mission's role is to make that development auditable statement by statement.
The polynomial-factor reductions of [OAI26, Song26] produce a linear system from each formula ; the code is and the target any solution. In the preprocessing model the matrix must depend on the input length alone, with entering only the right-hand side. Replacing the clause system by a fixed verifier circuit almost achieves this, but the instance still appears in the input equations as a coefficient, times a moment of an unknown table. The term cannot simply be moved to the right-hand side, because in an honest solution that moment depends on the witness, not on alone. Soundness has to be re-established for a system in which the formula is visible only through the target.
A second difficulty is quantitative: the gap must be in terms of the final block length or dimension , which is much larger than , so the size of every component of the construction must be controlled with explicit exponents.
Submodule F (M → F) over an arbitrary finite field F that is an algebra over ; distances are natural numbers (sInf of the Hamming distances, attained).IsZLattice and the distance with Metric.infDist in PiLp. The exponent ranges over all real and (the paper restricts to rational for computability).Tables.codeFamily and the lattice is Tables.latticeFamily, both defined from the fixed linear system of Construction 4.5. What is asserted to exist is the tables: a base and an explicit moment representation (Theorem A.8), which do not depend on the instance. The constant is existential in the goal; the milestones give it explicitly as sizeExp.Nonempty of a structure (CodeGap, LatticeGap) that bundles some code or lattice with targets, a radius and the bounds. This was the mission's first goal. Since the targets are not required to be computable, this form is also satisfied by a construction unrelated to the paper, in which the target records whether the instance is satisfiable. It is kept as milestones for reference; the statements to rely on are the ones for the paper's construction.ObliviousPCP), an arbitrary language and an arbitrary field: completeness, soundness and the block length of the accepting-view code. The copies of each block of the matrix are indexed by the queries , which gives the paper's matrix up to the order of its rows. The theorem assumes only and a lower bound on the relative distance, and needs neither nor . Its running-time claims are not formalized, and neither are the PCPs of Theorem 6.5, which the paper takes from the literature, or Corollary 6.6.CodeGap or LatticeGap: without the running-time bound, an abstract "test" field would be satisfied by membership in itself.theorem LatticePrepro.ThreeSAT.explicit_code_and_lattice_gaps :
(∀ (p : ℕ) [Fact p.Prime] (F : Type) [Field F] [Fintype F] [DecidableEq F]
[Algebra (ZMod p) F] (ε : ℝ), 0 < ε → ε < 1 →
∃ C : ℕ, ∀ v : ℕ, 1 ≤ v → ∃ T : (verifier p v).Tables (1 - ε),
((T.codeFamily F).comap encode).HasGap T.system.numBlocks ε (SAT v) (len v) C) ∧
(∀ (pn : PNorm) (ε : ℝ), 0 < ε → ε < 1 / pn.s →
∃ C : ℕ, ∀ v : ℕ, 1 ≤ v → ∃ T : (verifier 2 v).Tables (1 - pn.s * ε),
((T.latticeFamily pn).comap encode).HasGap pn (T.latticeRadius pn) ε (SAT v) (len v)
C) := by sorryInstances of 3SAT on variables are encoded as bit strings of length , one bit per possible clause, and is the quadratic verifier of the 3SAT verifier circuit over the relevant prime field. Tables for consist of a base and an explicit moment representation (Theorem A.8) in the ranges of the proof of Theorem 4.8; they do not depend on the instance. Both of the following hold.
This is the paper's Theorem 5.1 for the 3SAT verifier, stated for the code and the lattice that the paper constructs; it is the conjunction of ThreeSAT.explicit_code_gap and ThreeSAT.explicit_lattice_gap. The existence form of this statement only asserts that some code or lattice with targets has the gap. Since the Lean statement does not require the targets to be computable, that form is satisfied by a construction unrelated to the paper, in which the target records whether is in the language. Here the code, the lattice and the targets are the ones the paper constructs.
Formalization Note. Only the tables are asserted to exist; the code, the lattice, the targets and the radius are defined from them, and the instance enters through the right-hand side of the fixed linear system alone. Polynomial-time computability of the code, the lattice and the targets is not formalized. The target uses a solution of picked by classical choice, where the paper uses Gaussian elimination; the distance from the target to the code does not depend on the solution. The description lengths of Theorem 5.1 are not formalized either. The exponent ranges over all reals and (the paper takes it rational), and is a real power.
No open leaves. Every sub-goal is proved or awaiting decomposition.