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 (1|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.)