works on
coding theory 1lattice algorithms 1locally dense lattices 1np-hardness 1shortest vector problem 1

From the 1 of 2 linked papers with an AI index.

collaborators

2 papers

cs.CC2026

Euclidean SVP is deterministically NP-hard to approximate within any constant factor

Daqing Wan

We prove that, for every constant , the Euclidean shortest vector problem is NP-hard to approximate within any constant factor under a deterministic polynomial-time many-o…

math.NT2026

NP-hardness of SVP in Euclidean Space

Daqing Wan

The paper proves that computing the shortest non-zero vector of a lattice in Euclidean space is NP‑hard, confirming van Emde Boas's conjecture and giving a deterministic version of…