The Complexity of the Covering Radius Problem on Lattices and Codes
Venkatesan Guruswami, Daniele Micciancio, Oded Regev · 2007
We initiate the study of the computational complexity of the covering radius problem for point lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices.