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?)
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.