We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) code is hard. Later Dumer, Micciancio and Sudan showed that it is hard to approximate also. Both of them talk about hardness of the problem when all codes are considered.

My question is regarding a slightly more restricted class. Is there anything known for codes of half rate? Without loss of generality, parity check matrix of the code can be assumed to be of the form $(\mathbb{1 \vert }M)$ where $M$ is a square matrix. I assume that none of the results above directly give NP-hardness (for exact or approximate answer) when class is restricted since the reductions don't end up landing in half rate codes.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.