**Authors:** Venkatesan Guruswami, Daniele Micciancio, and
Oded Regev

Computational
Complexity **14**:90-120, 2005. [Invited paper. Preliminary
version in CCC 2004]

**Abstract:** 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. For the covering radius on n-dimensional lattices, we show
that the problem can be approximated within any constant factor gamma(n)
> 1 in random exponential time 2^{O(n)}, it is in AM for gamma(n) = 2, in
coAM for gamma(n) = sqrt{n / log n}, and in NP intersected coNP for gamma(n)
= sqrt{n}. For the covering radius on n-dimensional linear codes, we show
that the problem can be solved in deterministic polynomial time for
approximation factor gamma(n) = log n, but cannot be solved in polynomial
time for some gamma(n) = Omega(log log n) unless NP can be simulated in
deterministic n^{O(log log log n)} time. Moreover, we prove that the problem
is NP-hard for *any* constant approximation factor, it is Pi_2-hard
for *some* constant approximation factor, and it is in AM for
approximation factor 2. So, it is unlikely to be Pi_2-hard for any constant
approximation factor. This is a natural hardness of approximation result in
the polynomial hierarchy. For the shortest independent vectors problem, we
give a AM protocol achieving approximation factor gamma(n) = sqrt{n / log
n}, solving an open problem of Blomer and Seifert (STOC'99).