2 citations · 2 across the 3 of their papers we have counts for
5 papers
NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes
Daqing Wan, Jun Zhang
For an Reed--Solomon code, the covering radius is . Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding ra…
Euclidean SVP is NP-hard for Cyclic Lattices
Daqing Wan
We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\…
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…
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…
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…