# NP-hardness of minimum distance over a code

There happens to be this NP-complete question,

Minimum-Distance-Over-$\mathbb{F}_{2^m}$

Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in \mathbb{F}_{2^m}^n$ of weight $\leq w$ s.t $Hx=0$?

• Is there some "easy" proof of this? (as opposed to say what I can partly fish out of this paper, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542)

• Is there any variant of it where the hardness is true even if I assume that $H$ has at least $r$ linearly independent columns? (and such a condition gets automatically satisfied if the rows of $H$ define a code?)

• Maybe I don't understand your second question, but I think assuming that $H$ has $r$ linearly independent columns is without loss of generality. If $H$ has rank $r' < r$, then we can replace $H$ with a $r'\times n$ submatrix $H'$ whose rows form a basis for the rowspace of $H$. Then $H'x = 0$ if and only if $Hx = 0$ and $H'$ has rank $r'$ so it must have $r'$ linearly independent columns. As for the hardness reduction, I don't know what "easy" is, but did you read Vardy's paper ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542 ? – Sasho Nikolov Apr 8 '15 at 18:09
• @SashoNikolov Thanks for the explanation! I have indeed been trying to dig through Vardy's paper. But its quite a mess :D There is a complex network of reductions that its hardly clear to me as to which part is a proof of NP-hardness of this particular statement! Can you help decipher it? :D – Anirbit Apr 8 '15 at 18:33
• For the future: We expect you to do research on your own before asking the question, and to tell us in the question what research you've done, what you've found, and what you know. (For instance, if you already knew of that paper but had trouble understanding it, you should have mentioned this in the question -- leaving that out is a bit impolite to answerers who put in the effort only to have you tell them that you already knew that.) Showing what you've already tried is in your interest as it ultimately makes it more likely you get the kind of answer you are looking for. – D.W. Apr 9 '15 at 20:59
• Thanks! I guess I should have made it more explicit that I am looking for an alternative reference or approach to the Vardy's paper - which I find to be quite convoluted to decipher! – Anirbit Apr 9 '15 at 22:15
• @Turbo Ajtai has shown that SVP is hard under randomized reductions and Micciancio has shown a constant hardness of approximation (also using a randomized reduction). Moreover, the randomization can be removed using a number theoretic conjecture. I think you are confused about the consequences of such a hardness proof: maybe you are thinking of an approximation version of SVP with polynomial approximation factors. – Sasho Nikolov May 12 '15 at 8:08

Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf Diaconis and Graham prove that deciding if a binary code of length $2m$ contains a code word of weight $n$ is NP-complete.