Daqing Wan

most citedOn the List and Bounded Distance Decodibility of the Reed-Solomon Codes

2 citations · 2 across the 3 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2026

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

Daqing Wan, Jun Zhang

For an $[n, K]$ Reed--Solomon code, the covering radius is $n - K$ . Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding ra…

cs.CC2026

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:=\…

cs.CC2026

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

Daqing Wan

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