The Parameterized Complexity of Some Fundamental Problems in Coding Theory

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.