Abstract:
The parameterized complexity of a number of fundamental problems in the theory of linear
codes and integer lattices is explored. Concerning codes, the main results are that Maximum-
Likelihood Decoding and Weight Distribution are hard for the parametrized complexity class W[1]. The NP-completeness of these two problems was established by Berlekamp,
McEliece, and van Tilborg in 1978, using a reduction from 3-Dimensional Matching. On
the other hand, our proof of hardness for W[1] is based on a parametric polynomial-time
transformation from Perfect Code in graphs. An immediate consequence of our results
is that bounded-distance decoding is likely to be hard for linear codes. Concerning lattices,
we address the Theta Series problem of determining, for an integer lattice Λ and a positive
integer k, whether there is a vector xЄ Λ of Euclidean norm k. We prove here for the first
time that Theta Series is NP-complete, and show that it is also hard for W[1]. We furthermore prove that the Nearest Vector problem for integer lattices is hard for W[1]. These
problems are the counterparts of Weight Distribution and Maximum-Likelihood De-
coding for lattices, and are closely related to the well-known Shortest Vector problem.
Relations between all these problems and combinatorial problems in graphs are discussed.