Math Conjectures

Fixed-Polynomial-Factor Hardness of Euclidean Closest Vector

OPENMajorConjectureProposed c. 2003 · Standard version

Canonical statement

There exists a constant ε>0\varepsilon>0 for which the following promise problem is NPNP-hard under deterministic polynomial-time many-one reductions: given a lattice basis B∈Zm×nB\in\mathbb Z^{m\times n}, target t∈Zmt\in\mathbb Z^m, and radius r>0r>0, distinguish
dist⁡2(t,L(B))≤rfromdist⁡2(t,L(B))>nεr. \operatorname{dist}_2(t,L(B))\le r\quad\text{from}\quad\operatorname{dist}_2(t,L(B))>n^\varepsilon r.
View source LaTeX
There exists a constant \(\varepsilon>0\) for which the following promise problem is \(NP\)-hard under deterministic polynomial-time many-one reductions: given a lattice basis \(B\in\mathbb Z^{m\times n}\), target \(t\in\mathbb Z^m\), and radius \(r>0\), distinguish
\[
  \operatorname{dist}_2(t,L(B))\le r\quad\text{from}\quad\operatorname{dist}_2(t,L(B))>n^\varepsilon r.
\]
TCS-030:[DinurEtAl2003CVP][OpenAI2026TenAdvances]
Theoretical computer scienceDiscrete geometry

Notes

The Euclidean closest vector problem is a central lattice problem. Dinur, Kindler, Raz, and Safra proved deterministic hardness up to almost-polynomial factors [DinurEtAl2003CVP], leaving every fixed power nεn^\varepsilon beyond reach. The August 1, 2026 manuscript claims a direct 3SAT reduction with exponent 1/4001/400 [OpenAI2026TenAdvances]. Until the reduction and gap preservation are independently checked, the target remains open in the stable catalog.

Proof-claim watch (1)

Fixed-polynomial-factor hardness of Euclidean CVP

Grade C

Full target hardness claim awaiting independent verification.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.