3 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
In 1981, van Emde Boas conjectured that computing a shortest non-zero vector of a lattice in a Euclidean space is -hard. In this paper, we prove this conjecture, there…
math.NT2004
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes
Qi Cheng, Daqing Wan
In this paper show that the list and bounded-distance decoding problems of certain bounds for the Reed-Solomon code are at least as hard as the discrete logarithm problem over fini…