*Bounty: 100*

*Bounty: 100*

It has been shown by Vardy that minimum distance of a code is NP-hard (see Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757–1766.) Similar and related results were also proved in the following : Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] and by Dumer, Micciancio and Sudan. The former showing hardness in the case of binary codes whereas the later shows a similar result for approximation version.

Most of these show worst case hardness knowing no additional information about code (other than k and n).

In particular, these problems assume no bounds on rate or distance.

Certainly, a "promise" version could be easier as a trivial example consider a promise that code family is of some bounded constant distance. Clearly a brute algorithm by enumeration would find minimum distance in poly time.

As far as I see the DMS reduction works only for codes with minimum distance that is linear in the dimension.

Has the problem been studies for different d (sublinear) either in exact or approximate version?