How hard is the nearest lattice point?
Given a target, how hard is it to find the closest point on a high-dimensional lattice?
Lattice cryptography has made the closest vector problem famous, but the theorem here is a complexity result before it is a security result. The manuscript gives a deterministic reduction from ordinary 3SAT showing that even an n1/400-factor approximation to Euclidean CVP is NP-hard.1manuscript The fixed exponent is tiny. The qualitative jump is not: the previous unconditional exponent faded toward zero as dimension grew.4Dinur
A concrete starting point
A two-dimensional lattice is a regular array of points generated by two independent vectors. Given a target between those points, the closest vector problem asks for the nearest lattice point. CVP poses the same question when the lattice has hundreds or thousands of independent directions.1manuscript
The gap version is more forgiving. You only need to distinguish “a lattice point is within distance r” from “every lattice point is farther than γr.” If the true answer lies in between, either response is allowed. An approximation factor γ = n1/400 grows painfully slowly, but it keeps growing as dimension n increases.1manuscript
The reduction turns a 3SAT formula into binary evaluation tables. A sufficiently low-weight solution must encode one consistent satisfying assignment. A parity construction then turns the number of selected bits into squared Euclidean distance, so a solver for the resulting gap instance would decide whether the formula was satisfiable.1manuscript2walkthrough
Move the target between lattice points
The highlighted grid point is the exact nearest point. GapCVP asks only whether the distance is definitely small or definitely larger by a promised factor.
YES if distance ≤ r. NO if distance > γr. In between, either answer is allowed. The theorem uses γ(n) = n1/400; the slider only illustrates the promise gap.
The problem and the promise gap
A nonsingular integer matrix B generates the lattice L(B) = {Bz : z ∈ ℤn}. Given a target t, CVP minimizes ‖t − Bz‖₂. GapCVP(2)γ promises either a YES instance with distance at most r or a NO instance with distance strictly greater than γ(n)r.1manuscript
NP-hardness is a statement about worst-case computation: a polynomial-time algorithm solving every promised instance would give polynomial-time algorithms for all problems in NP. It is not an algorithm for finding lattice points, nor does it claim that most naturally occurring instances are hard.
The earlier frontier—and why “almost polynomial” was not enough
Exact CVP was known NP-hard in 1981, and 1990s work extended hardness to every fixed constant approximation factor.1manuscript Dinur, Kindler, Raz, and Safra then proved unconditional hardness within na/log log n for some constant a > 0.4Dinur That factor grows faster than any fixed power of log n, but its exponent a/log log n tends to zero. It therefore does not imply hardness for nc with any fixed positive c.1manuscript
Fixed-polynomial hardness had been obtained under stronger conjectural assumptions, including the Projection Games Conjecture. The target here was a deterministic many-one reduction from ordinary 3SAT, with no randomized step, gap-producing PCP, or projection-games assumption.
Three bottlenecks
First, a binary Hamming gap G becomes only √G after moving to Euclidean distance because ‖u − v‖₂² equals Hamming distance for binary vectors. Second, repeatedly tensoring a constant gap can enlarge the dimension so quickly that the reduction ceases to be polynomial. Third, signed or integer gadgets permit cancellation: locally inconsistent choices may cancel into a falsely short global object.2walkthrough
There is also a known ceiling nearby. Aharonov and Regev placed GapCVP at a constant multiple of √n in NP ∩ coNP.5Aharonov NP-hardness at that scale would imply NP = coNP, so the open range between exponents 1/400 and 1/2 is not expected to yield casually.
Characteristic-two tables make cancellation visible
Work over a finite field K of characteristic two, where 1 + 1 = 0. Choose a field anchor ai for every Boolean variable. An assignment σ determines the unique low-degree interpolation polynomial Qσ with Qσ(ai) = σi; this is the Reed–Solomon viewpoint.6Reed
For every evaluation point p and possible value w, a binary indicator xτ,p,w records whether table type τ selects w at p. There is one global table and, for each clause, a table for each satisfying local assignment. Parity constraints say that every global fiber has odd size and that the satisfying clause tables reproduce the global table modulo two.1manuscript
The constraints also record ordinary power sums μτ,j(p) = Σ xτ,p,wwj and shifted power sums centered at the variable anchors. Although they look nonlinear, every power of p and w is a known field coefficient; the only unknown is the bit x. Reed–Solomon membership becomes linear parity checks, yielding one explicit binary affine system Hx = b.1manuscript2walkthrough
Hankel reconstruction in characteristic two
A low-Hamming-weight solution selects only a few w-values in most fibers. Their power sums form a Hankel matrix—entries depend only on the sum of the row and column indices. At a maximum-size fiber of h distinct values, its determinant is the square of a Vandermonde product and is nonzero.1manuscript
That nonzero determinant gives a recurrence and reconstructs a monic separable polynomial Gτ(Y) over K(X). Its distinct algebraic roots reproduce all prescribed moments, not just the initial Hankel window.1manuscript The proof carefully avoids dividing by Newton coefficients that vanish in characteristic two; separability comes from distinct fiber values and the Vandermonde determinant.2walkthrough
The zeroth global moment records parity, not ordinary cardinality. Its value is odd, so the global reconstructed root set is nonempty. Here characteristic two stops being a nuisance and becomes the selection mechanism.
Shifted moments synchronize every clause
Ordinary moments reconstruct candidate algebraic roots but do not label them with Boolean bits. The shifted moment around anchor ai measures powers of (w − βi)/(p − ai). A valuation argument forces any reconstructed clause root α to satisfy vi(α − βi) ≥ 1.1manuscript2walkthrough
The proof puts all roots into one common splitting field and uses compatible extended valuations. If two clause choices assigned different bits to the same variable, both α − 0 and α − 1 would vanish at that anchor; the ultrametric inequality would absurdly force 1 to vanish too. Thus one global root carries mutually compatible local choices and yields a satisfying assignment.2walkthrough This is the soundness engine: low weight cannot be assembled from mutually inconsistent local stories.
The parity lift turns weight into distance
From Hx = b, choose one binary solution u and define ΛH as all integer vectors z whose residues modulo 2 satisfy H(z mod 2) = 0. Then, for every p ≥ 1,
minz∈ΛH ‖u − z‖pp = min{wt(x) : Hx = b}.
Every odd coordinate costs at least 1, and every binary affine solution attains its Hamming weight. For Euclidean distance p = 2, taking a square root turns a binary n1/200 gap into a lattice n1/400 gap.1manuscript This decoding-to-lattice relationship traces back through classical coding-hardness work.7Berlekamp
Parity prevents hidden cancellation → Hankel moments rebuild a small root set → anchor valuations force one consistent Boolean assignment → the parity lattice converts weight to exact distance.1manuscript7Berlekamp
The proof map
- Encode assignments. Polynomial evaluation tables represent a global assignment and its satisfying restriction to every clause; all constraints remain binary-linear.1manuscript
- Exploit low weight. Discard a small exceptional set separately for each table type so the remaining fibers are small without exhausting the parameter budget.2walkthrough
- Reconstruct roots. Hankel determinants and Vandermonde factorization recover separable algebraic root sets with the required full moment sequence.1manuscript
- Synchronize clauses. Parity guarantees a global root, while shifted moments and valuations make its local satisfying assignments agree on shared variables.1manuscript2walkthrough
- Lift to CVP. Convert Hx = b to an explicit square integer lattice basis, with Hamming weight equal to p-th-power distance.1manuscript
Technical layer · where 1/400 comes from
For a 3SAT input-size parameter N, the construction chooses a field of size q = Θ(N200), a fiber bound K = N4, and a moment budget T = N30. The binary block length M—and therefore the lattice rank—is at most 40N401.1manuscript2walkthrough These exponents are large but fixed, so the reduction is polynomial-time.
Completeness gives a binary solution of weight R. Soundness proves that a solution of weight at most 4M1/200R would reconstruct a satisfying assignment. Choosing an integer radius r = ⌈√R⌉ gives r² ≤ 4R; the factor four absorbs rounding and preserves a strict NO inequality.2walkthrough
Since the Euclidean norm is the square root of binary weight, the soundness ratio M1/200 becomes M1/400. More generally, the ℓp norm takes the p-th root and gives M1/(200p) for every fixed rational p ≥ 1.1manuscript
The exact theorem and related consequences
Theorem 1 gives a deterministic polynomial-time many-one map from each 3SAT formula φ to a nonsingular square integer basis B, integer target t, and positive rational radius r. If φ is satisfiable, the distance is at most r; if φ is unsatisfiable, it is strictly greater than n1/400r. Therefore GapCVP₂ with factor n1/400 is NP-hard.1manuscript
The same construction yields n1/200-factor NP-hardness for binary nearest codeword and syndrome decoding, and n1/(200p) for CVP in every fixed rational ℓp norm with p ≥ 1.1manuscript The released Comparator manifest names all four results and their promise definitions.3formal artifact
A related Reed–Solomon lattice lift appeared in Bennett and Peikert’s randomized hardness reduction for shortest vector; this theorem instead gives a deterministic reduction for closest vector.8Bennett
What this does—and does not—say about cryptography
The result concerns worst-case, general, explicit lattices. Modern lattice cryptography uses particular structured or average-case problems and separate reductions. The theorem neither breaks standardized post-quantum systems nor directly proves them secure.1manuscript It strengthens the complexity landscape around a foundational lattice problem.
Nor is 1/400 close to a final threshold. It is a qualitative fixed-power breakthrough, not a practical approximation guarantee. The interval up to the square-root barrier remains open.1manuscript
Is the claim overhyped?
My calibrated verdict: a major unconditional complexity result if independently validated, with a deliberately modest exponent and no direct claim about deployed cryptosystems.
Euclidean GapCVP is NP-hard to approximate within n^{1/400} under a deterministic reduction from 3SAT.
That is the manuscript’s main theorem and the primary GapCVP Comparator target.1manuscript3formal artifact
This crosses from an exponent tending to zero to a fixed positive exponent.
The prior unconditional benchmark was na/log log n; 1/400 remains fixed as n grows.4Dinur1manuscript
The result breaks lattice cryptography.
No. Worst-case hardness for general CVP does not constitute an attack on the structured or average-case assumptions used by standardized schemes.1manuscript
The released formalization makes independent review unnecessary.
The formal targets are substantial evidence. Specialists still need to audit promise encodings, dimension bookkeeping, imported algebraic claims, and the match between formal and prose statements.3formal artifact9announcement
Full bibliography
9 fully annotated sources
- 01 · primary manuscript
OpenAI. Ten Advances in Mathematics and Theoretical Computer Science — Chapter 7, abstract, Theorem 1, and §§1–7, PDF pp. 183–215. Primary source for the reduction, exact exponents, dimension bound, reconstruction, parity lift, and consequences. ↩
- 02 · reasoning walkthrough
OpenAI. Reasoning Walkthroughs — Chapter 8, §§8.1–8.6, PDF pp. 37–40. Explains the signed-histogram detour, cancellation bottleneck, characteristic-two reconstruction, anchor valuations, and exact exponent. ↩
- 03 · formal certificate
OpenAI. GapCVP.lean and Comparator challenge — gapCVP400IsNPHard, binaryNearestCodewordIsNPHard, binarySyndromeDecodingIsNPHard, and finitePNormGapCVPIsNPHard; commit e62211d. OpenAI-authored Lean targets and promise definitions from the same release; useful for auditability, but not independent review. ↩
- 04 · peer-reviewed predecessor
Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within almost-polynomial factors is NP-hard — Combinatorica 23, 205–243 (2003). The prior unconditional n^{a/log log n} approximation-hardness benchmark. ↩
- 05 · peer-reviewed predecessor
Dorit Aharonov and Oded Regev. Lattice problems in NP intersect coNP — Journal of the ACM 52(5), 749–765 (2005). Places GapCVP at a constant multiple of the square-root scale in NP ∩ coNP. ↩
- 06 · peer-reviewed predecessor
Irving S. Reed and Gustave Solomon. Polynomial codes over certain finite fields — Journal of the Society for Industrial and Applied Mathematics 8(2), 300–304 (1960). Primary source for polynomial evaluation codes underlying the table constraints. ↩
- 07 · peer-reviewed predecessor
Elwyn Berlekamp, Robert McEliece, and Henk van Tilborg. On the inherent intractability of certain coding problems — IEEE Transactions on Information Theory 24(3), 384–386 (1978). Classical hardness source for syndrome decoding and the coding-to-lattice relationship. ↩
- 08 · peer-reviewed predecessor
Huck Bennett and Chris Peikert. Hardness of the shortest vector problem via Reed–Solomon codes — APPROX/RANDOM 2023, Article 37. A related Reed–Solomon lattice lift in a randomized reduction for SVP; the present route is deterministic and targets CVP. ↩
- 09 · official announcement
OpenAI. Ten advances in mathematics and theoretical computer science — “How the results were developed” and “Verification” sections. Used only for OpenAI’s process description, not theorem correctness. ↩