We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary) code is hard. Later Dumer, Micciancio and Sudan showed that it is hard to approximate also. Both of these papers 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 $[I|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.

(Note: I asked this question on TheoryCS stack and it was unanswered even after a bounty period was over. Moderator suggested me to cross put it on mathoverflow. Here is the link to the first question. For the sake of being self-contained I will also write the question here.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.