#StackBounty: #np-hardness #approximation-hardness #np-complete #coding-theory For what parameters is minimum distance hard?

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?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.