NP-hardness of SVP in Euclidean Space

Daqing Wan

REVIEW 1 major objections 4 minor 1 cited by

NP-hardness of SVP in Euclidean Space

T0 review · 1 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that finding a shortest nonzero vector in a Euclidean lattice is NP-hard, resolving a conjecture that has been open since 1981.

desk verdict A serious, well-structured proof of the long-standing conjecture, but the whole edifice leans on one self-cited Betti-number bound whose failure would collapse the argument; worth refereeing, not yet settled. read the letter →

arxiv 2603.27398 v3 pith:XTYU22AZ submitted 2026-03-28 math.NT cs.CC

Daqing Wan This is my paper · ORCID

classification math.NTcs.CC MSC 11H0668Q1714G1594B27

keywords shortestvectorproblemNP-hardnesslatticesReed-SolomoncodeslocallydenseWeilconjecturescompleteintersectionsdeterministicreduction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that computing a shortest nonzero vector in a lattice (SVP) is NP-hard, settling the 1981 van Emde Boas conjecture. More generally, it shows that for every p ≥ 1 and every approximation factor γ < 2^{1/p}, the γ-approximate decision version of SVP in the ℓ_p norm is NP-hard. The proof is fully deterministic, removing the randomness from a celebrated 1998 hardness reduction. A sympathetic reader should care because this settles the fundamental complexity question for lattice problems and supplies the first deterministic hardness proof for the exact Euclidean case.

What carries the argument

The central object is the Reed-Solomon lattice L_{q,k} = {v ∈ Z^q : H_q(k)v ≡ 0 mod q}, the integer lifting of the dual of a Reed-Solomon code, whose minimum ℓ_p distance is at least (2k)^{1/p}. The argument's engine is a point-count estimate for the affine complete intersection X_{k,h,u}: sum_{i=1}^h x_i^j = h_j for j = 1..k-1, obtained by comparing its zeta function with the Weil bound and using a companion Betti-number bound to control the constant. Inclusion-exclusion sieving removes repeated coordinates and enforces the projection property that yields the locally dense lattice in the strong sense.

What would settle it

For small primes q and chosen parameters k, h, compute the number of F_q-rational points on X_{k,h,u} and check the claimed bound |N_h(q) - q^{h-k+1}| ≤ ½(2k)^h q^{(h-k+2)/2}; a single violation would invalidate the proof. Alternatively, for a concrete q, k, h, r satisfying the theorem's constraints, enumerate the binary vectors in the coset y + L_{q,k} and verify that their projection to the first r coordinates covers all of {0,1}^r.

Watch

Extended reading notes

Core claim

The central claim is that an explicitly constructed Reed-Solomon lattice L_{q,k} together with a fixed binary vector y is a locally dense lattice with a provable bad center: the coset y + L_{q,k} contains subexponentially many short binary vectors, and the projection of these vectors onto the first r coordinates covers all of {0,1}^r. The proof counts such vectors by relating them to F_q-rational points on the complete intersection variety X_{k,h,u}, defined by power-sum equations in h variables. Using Deligne's Weil conjectures and a companion bound on total Betti numbers, the paper shows these point counts are large enough to make the lattice locally dense, leading to Theorem 7.4: for ever

Load-bearing premise

The entire proof rests on a companion theorem bounding the total Betti number of certain affine complete intersection varieties; if that bound is false or does not apply to the varieties X_{k,h,u} and Y_{k,h,u}, the point-count estimates — and with them the construction of the bad center — collapse.

Editorial extensions

If this is right

SVP is not in polynomial time unless P = NP, closing a 41-year-old open problem.
The exact shortest vector problem in Euclidean space is deterministically NP-hard, eliminating the need for randomized reductions.
The same deterministic hardness holds for the ℓ_p norm for every p ≥ 1 for approximation factors below 2^{1/p}.
The explicit locally dense lattice construction gives Reed-Solomon list-decoding configurations with agreement-to-dimension ratio arbitrarily large, improving on prior explicit regimes.
Lattice-based cryptography: while exact hardness of SVP does not directly imply hardness of commonly used polynomial-approximation problems, it sharpens the known complexity boundary for lattice problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The counting method may generalize to other families of algebraic-geometric codes, since it only requires the underlying varieties to be complete intersections with controlled Betti numbers.
If the companion Betti bound failed for the specific singular varieties X_{k,h,u} and Y_{k,h,u}, the proof's point-count estimates would break; a direct computational check for small primes q would provide a cheap sanity test.
The hardness threshold γ < 2^{1/p} lies below the polynomial approximation factors used in most lattice-based cryptography, so the result is primarily a complexity classification rather than a practical cryptanalytic threat.
Combining this construction with PCP-based approaches for p > 2 might extend deterministic hardness to larger approximation factors, though that remains a conjecture.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this preprint claims to settle van Emde Boas's conjecture: deterministic NP-hardness of SVP, and more generally gamma-GapSVP_p for 1 <= gamma < 2^{1/p}. The route is a derandomization of Bennett-Peikert using an explicit Reed-Solomon lattice and an explicit bad center; the key input is Deligne plus a total Betti number bound from the author's own [WZ26]. I read through the main line and it is coherent and genuinely new. The variety is a complete intersection, the singular locus is controlled, the inclusion-exclusion is standard, and the parameter bookkeeping in section 7 is intricate but consistent. The theorem as stated is not in the cited literature: Ajtai and Bennett-Peikert are randomized, and the deterministic results for p > 2 don't cover p = 2. If the arithmetic-geometry input holds, this is a major result.

The soft spot is exactly where the reader's report puts it: Proposition 5.2 uses [WZ26, Thm 1.2.2] to get the constant (1/2)(2k)^h in the error term. That constant is load-bearing. If you replace it with Katz's standard estimate 3(k+1)^{h+k}, the error term has size about q^{epsilon1(2+epsilon)k + (h-k+2)/2}, which under the paper's own admissible choice epsilon1 < epsilon/(2(1+epsilon)) is comparable to or larger than the main term q^{h-k+1}. So Theorems 6.3, 7.3, and 7.4 all collapse unless [WZ26] is exactly right and applicable. I don't see an internal contradiction, and citing a published companion paper is not itself a flaw, but this is a single point of failure. The paper would be much stronger if it sketched the proof of that bound for this specific family, or if an independent verification existed.

A few smaller issues: the text has typographical noise (author names, a few misspellings), and Remark 1.9's coding-theoretic bonus is stated without proof details, though Corollary 6.4 gives the argument. None of that affects the mathematics.

Bottom line: this deserves a serious referee. The result is important, the argument is plausible, and the dependency is explicit. I would send it to peer review immediately, with instructions to check [WZ26] first. My own verdict is conditional: I wouldn't bet the conjecture is settled until that Betti bound is independently confirmed.

Referee Report

1 major / 4 minor

Summary. The paper claims to prove Conjecture 1.1 (van Emde Boas) that SVP in Euclidean space is NP-hard, and more generally that γ-GapSVP_p is NP-hard for every p≥1 and 1≤γ<2^{1/p}. The strategy follows Micciancio's derandomization program: use a Reed-Solomon lattice L_{q,k} with an explicit bad center y, show it is locally dense with projection by lower-bounding the number of binary vectors in a coset via point counts on the complete intersections X_{k,h,u}, Y_{k,h,u}, and Z_x, and then invoke [BP23, Cor. 2.11]. The point-count estimates use Deligne's Weil-conjectures theorem and an explicit total Betti number bound imported from the author's companion paper [WZ26]. The final theorem is stated unconditionally.

Significance. Conditional on the correctness of [WZ26, Thm 1.2.2], this would be a landmark result: it settles a longstanding conjecture, removes randomness from Ajtai's hardness theorem, and gives the first explicit deterministic construction of locally dense lattices with bad centers in the regime α∈(2^{-1/p},1). The construction is simple and the parameter choices are coherent. The paper also gives a coding-theoretic corollary (Corollary 6.4) with an explicit Reed-Solomon list-decoding configuration. The proof is not machine-checked, but it is structured and mostly self-contained apart from the cited Betti bound and the reduction theorem.

major comments (1)

[§5, Prop. 5.2 and 5.3] The numerical constant in the central estimate is entirely supplied by the cited companion theorem [WZ26, Thm 1.2.2], stated as Prop. 5.3. This is load-bearing: Prop. 5.2 gives |N_h(q)-q^{h-k+1}| ≤ 1/2(2k)^h q^{(h-k+2)/2}; the factor 1/2(2k)^h is obtained only from the [WZ26] bound ≤ binom(h-1,k-2)k^h < 2^{h-1}k^h. If, as the paper itself notes, one uses Katz's estimate 3(k+1)^{h+k-1}, then with h≈(1+ε)k and 2k=⌊q^{ε1}⌋ the error term is about q^{ε1(2+ε)k + (h-k+2)/2}, while the main term is q^{h-k+1}=q^{εk}. Under the admissible choice ε1<ε/(2(1+ε)) this error is no longer dominated by the main term; the inequalities (6.3.1), (6.3.2), (7.2.3) and hence Theorems 6.3 and 7.3 collapse. Thus the unconditional statement of Theorem 7.4 is exactly as strong as the unproved companion result. The author should either include a proof of the needed special case of [WZ26, Thm 1.2.2] in this paper o

minor comments (4)

[General] Typographical and reference inconsistencies: title 'SP ACE', 'Bennet-Peifert' vs 'Bennett and Peikert', 'Definiction', and the arXiv number of [BP23] is not given. These should be cleaned up.
[§4, Prop. 4.2] The displayed chain of inequalities for dimensions is easy to misread; the direction '≥' is correct after rearranging 'adding an equation lowers dimension by at most one', but the notation makes the argument appear to claim the opposite. Rephrase.
[§7, after Prop. 7.2] The projection map is written A:S_2(h,q)→{0,1}^r; this should be S_2(y,h). Also the notation X_{k,h,u} is used for both affine and projective varieties in §§3–4; a disambiguating superscript would improve readability.
[§5, Prop. 5.2] The constants C_1,C_2 are said to be independent of q, but they may depend on k and h, which grow with q; this is harmless after the zeta-function argument, but the wording is imprecise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the local-density property is derived from Deligne-style point counts, and the only same-author citation is an independent Betti-bound theorem.

full rationale

The derivation chain is not circular. Theorem 7.4 follows from the external reduction theorem [BP23, Cor. 2.11] (Theorem 2.2) plus Theorem 7.3, which explicitly constructs the Reed–Solomon lattice L_{q,k} and the bad center y. The locally dense property is proved, not assumed: conditions (1) and (2) in Theorem 7.3 are established by Lemma 3.2 for the minimum distance and by lower bounds on the fiber sizes |Z^{**}_x(F_q)| obtained from the point-count estimates in Propositions 5.2 and 6.2 together with the inclusion-exclusion sieving inequality (7.2.2). The parameter choices (k, h, r, ε, ε1) are selected inside the proof to make the main term dominate the error terms; they are not fitted to any target quantity. The one self-citation that could attract attention is [WZ26, Theorem 1.2.2], used as Proposition 5.3 to bound total ℓ-adic Betti numbers of affine complete intersections. That is a general theorem about Betti numbers; it contains no lattice, SVP, or NP-hardness content, and it does not assume the local-density property or any form of the main theorem. It is therefore independent support, not a disguised restatement of the target. If [WZ26] were false or inapplicable, the paper's error-term constants would fail and Theorems 6.3 and 7.4 would collapse, but that is a correctness risk, not circularity. No equation in the paper equals its input by construction, and no known result is merely renamed as a new contribution. Hence no significant circularity is present.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical or combinatorial entities are postulated. The proof relies on a chain of external mathematical results, one of which ([WZ26]) is self-cited and load-bearing; the free parameters ε, ε_1, δ are choices of scale, not fitted constants.

free parameters (3)

epsilon (0 < ε < 1)
Chosen by hand to set the local-density fraction α = ((1+ε)/2)^{1/p}; letting ε → 0 pushes the hardness factor to 2^{1/p}. Not fitted to data; the theorem holds for any such ε.
epsilon_1 (0 < ε_1 < ε/(2(1+ε)))
Chosen by hand to set the code dimension scale k = floor(q^{ε_1}/2). It controls the subexponential size of the short-vector set and the projection dimension.
delta (0 < δ < ε_1)
Chosen by hand to set the projection dimension r = floor(q^δ). The existence of some δ in this range suffices for the reduction to poly(r) time.

assumptions (5)

standard math Deligne's theorem on the Weil conjectures (Weil II) [De81]
Used in Proposition 5.1/5.2 to bound deviations of point counts on complete intersections from the expected main term; a standard but deep theorem explicitly invoked in §5.
standard math Hooley-Katz singular complete-intersection point-count estimate (Proposition 5.1)
Stated as Proposition 5.1 with references to [Hoo91] and [Kat99]; used for X_{k,h,u}, X_{k,h}, and their hyperplane sections in §5 and §6. Not proved in this paper.
domain assumption Total ℓ-adic Betti number bound [WZ26, Theorem 1.2.2]
Imported from a companion paper co-authored by the present author; controls the constants in Propositions 5.2 and 6.2. If this bound is false, the exponential lower bounds on |S_2(y,h)| and the projection fibers fail.
domain assumption Reduction from GapSVP hardness to deterministic locally dense lattices [BP23, Corollary 2.11]
Theorem 2.2 converts the locally dense lattice construction into NP-hardness for γ-GapSVP_p; assumed from Bennett-Peikert's prior work.
standard math Newton's identities over F_q with h < q
Used in Lemma 3.2 and Proposition 4.2 to recover elementary symmetric polynomials from power sums; requires h below the field characteristic.

how reviews work

0 comments

Cite this review

Pith. "Pith review of NP-hardness of SVP in Euclidean Space." pith.science (2026). https://pith.science/paper/XTYU22AZ

@misc{pith2026260327398,
  author       = {Pith},
  title        = {Pith review of: NP-hardness of SVP in Euclidean Space},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XTYU22AZ}},
  note         = {Machine review of arXiv:2603.27398}
}

abstract

In 1981, van Emde Boas conjectured that computing a shortest non-zero vector of a lattice in a Euclidean space is $\mathbf{NP}$-hard. In this paper, we prove this conjecture, thereby derandomizing Ajtai's classical randomized hardness result (1998). We follow the derandomization program formulated by Micciancio (1998--2014) who conjectured the existence of an efficient deterministic construction of locally dense lattices. The key is to resolve this conjecture. Our proof builds on the candidate construction via Reed-Solomon codes by Bennett and Peikert (2023), and depends crucially on Deligne's work on the Weil conjectures for higher-dimensional varieties over finite fields.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

When Do Subset Sums in Finite Abelian Groups Support $2$-Designs?
math.CO 2026-07 accept novelty 6.0 of 10

For any finite abelian G and any target sum x, the k-subset family summing to x is a nontrivial 2-design only if G is an elementary abelian p-group.

Reference graph

Works this paper leans on

41 extracted references · cited by 1 Pith paper

[1]

M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108, 1996

1996
[2]

M. Ajtai. The shortest vector problem in L_2 is NP-hard for randomized reductions (extended abstract). In STOC , pages 10–19. 1998

1998
[3]

Aharonov and O

D. Aharonov and O. Regev. Lattice problems in NP coNP. J. ACM , 52(5):749-765, 2005. Preliminary version in FOCS . 2004

2005
[4]

Bennett and C

H. Bennett and C. Peikert. Hardness of the (approximate) shortest vector problem: a simple proof via Reed-Solomon codes. In Random , 2023

2023
[5]

H. Bennett. The complexity of the shortest vector problem. ACM SIGACT News 54 (1), pp. 37-61, 2023

2023
[6]

D. Boneh. Twenty years of attacks on the RSA cryptosystem. Not. of the Am. Math. Soc., 46(2):203-213, 1999

1999
[7]

Cai and A

J. Cai and A. Nerurkar. Approximating the SVP to within a factor (1 + 1/dim ) is NP-hard under randomized reductions. In CCC . 1998

1998
[8]

Cheng and D

Q. Cheng and D. Wan. On the list and bounded distance decodibility of the Reed-Solomon codes (extended abstract). In FOCS . 2004

2004

Show all 41 references

[9]

Cheng and D

Q. Cheng and D. Wan. A deterministic reduction for the gap minimum distance problem. IEEE Trans. Inf. Theory , 58(11):6935–6941, 2012. Preliminary version in STOC 2009

2012
[10]

Conway and N

J. Conway and N. J. A. Sloane. Sphere packings, lattices, and groups. Springer, 1999

1999
[11]

Coppersmith

D. Coppersmith. Finding small solutions to small degree polynomials. In Cryptography and Lattices , International Conference. 2001

2001
[12]

P. Deligne. La conjecture de Weil II. Publ. Math. IHES , 52(1981), 313-428

1981
[13]

Dumer, D

I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory , 2003. Preliminary version in FOCS 1999

2003
[14]

C. F. Gauss. Disquisitiones Arithmeticae. Gerh. Fleischer Iun, 1801
[15]

Goldreich and S

O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. , 60(3):540–563, 2000. Preliminary version in STOC 1998

2000
[16]

Guruswami and A

V. Guruswami and A. Rudra. Limits to list decoding Reed-Solomon codes. IEEE Trans. Inf. Theory , 52(8):3642–3649, 2006. Preliminary version in STOC 2005

2006
[17]

Haviv and O

I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory Comput. , 8(1):513–531, 2012. Preliminary version in STOC 2007

2012
[18]

Hair and A

I. Hair and A. Sahai. SVP _p is deterministically NP -hard for all p>2 , even to approximate with a factor of 2^ ^ 1- n . STOC (2026),. arXiv:2511.04125

2026
[19]

Hecht and M

Y. Hecht and M. Safra. Deterministic hardness of approximation of unique-SVP and GapSVP in _p -norms for p > 2 . STOC (2026). arXiv:2510.16991

2026
[20]

Hittmeir

M. Hittmeir. Fine-grained determisitic hardness of the shortest vector problem. arXiv:2511.01626
[21]

C. Hooley. On the number of points on a complete intersection over a finite field, with an appendix by N. M. Katz. J. Number Theory , 38 (1991), no. 3, 338-358

1991
[22]

R. Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987

1987
[23]

N. Katz. Estimates for ``singular'' exponential sums. Internat. Math. Res. Notices , 1999, no. 16, 875-899

1999
[24]

N. Katz. Sums of Betti numbers in arbitrary characteristic. Dedicated to Professor Chao Ko on the occasion of his 90th birthday. Finite Fields Appl. , 7 (2001), no. 1, 29-44

2001
[25]

S. Khot. Hardness of approximating the shortest vector problem in high _p norms. J. Comput. Syst. Sci. , 72(2):206–219, 2006. Preliminary version in FOCS 2003

2006
[26]

S. Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM , 52(5):789–808, 2005. Preliminary version in FOCS 2004

2005
[27]

Khot and P

S. Khot and P. Austrin. A simple deterministic reduction for the gap minimum distance of code problem. In Proceedings of ICALP , pages 474-485, 2011

2011
[28]

J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. J. ACM , 32(1):229-246, 1985

1985
[29]

T. Lai, A. Marino, A. Robinson, D. Wan. Moment subset sums over finite fields. Finite Fields Appl. , 62 (2020), 101607, 25 pp

2020
[30]

A. K. Lenstra, H. W. Lenstra, Jr., and L. Lov\'asz. Factoring polynomials with rational coefficients. Mathematische Annalen , 261(4):515-534, December 1982

1982
[31]

H. W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res. , 8(4):538-548, 1983

1983
[32]

Micciancio

D. Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. , 30(6):2008–2035, 2000. Preliminary version in FOCS 1998

2008
[33]

Micciancio and S

D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: a crypto- graphic perspective. Volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 2002. 488, 503

2002
[34]

Micciancio

D. Micciancio. Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory Comput. , 8(1):487–512, 2012

2012
[35]

Micciancio

D. Micciancio. Locally dense codes. In CCC . 2014

2014
[36]

C. Peikert. Limits on the hardness of lattice problems in _p norms. Computational Complexity , 17(2):300–351, May 2008. Preliminary version in CCC 2007

2008
[37]

C. Peikert. A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. , 10(4):283–424, 2016

2016
[38]

Regev and R

O. Regev and R. Rosen. Lattice problems and norm embeddings. In STOC . 2006

2006
[39]

van Emde Boas

P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report, 1981. Available at https://staff.fnwi.uva.nl/p. vanemdeboas/vectors/mi8104c.html

1981
[40]

Wan and D

D. Wan and D. Zhang. Betti number bounds for varieties and exponential sums. Adv. Math. , Vol 490 (2026), 110852

2026
[41]

C. Zong. The mathematical foundation of post-quantum cryptography. Research , 8 (2025), 1-12

2025

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108, 1996

1996

[2] [2]

M. Ajtai. The shortest vector problem in L_2 is NP-hard for randomized reductions (extended abstract). In STOC , pages 10–19. 1998

1998

[3] [3]

Aharonov and O

D. Aharonov and O. Regev. Lattice problems in NP coNP. J. ACM , 52(5):749-765, 2005. Preliminary version in FOCS . 2004

2005

[4] [4]

Bennett and C

H. Bennett and C. Peikert. Hardness of the (approximate) shortest vector problem: a simple proof via Reed-Solomon codes. In Random , 2023

2023

[5] [5]

H. Bennett. The complexity of the shortest vector problem. ACM SIGACT News 54 (1), pp. 37-61, 2023

2023

[6] [6]

D. Boneh. Twenty years of attacks on the RSA cryptosystem. Not. of the Am. Math. Soc., 46(2):203-213, 1999

1999

[7] [7]

Cai and A

J. Cai and A. Nerurkar. Approximating the SVP to within a factor (1 + 1/dim ) is NP-hard under randomized reductions. In CCC . 1998

1998

[8] [8]

Cheng and D

Q. Cheng and D. Wan. On the list and bounded distance decodibility of the Reed-Solomon codes (extended abstract). In FOCS . 2004

2004