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?

  • 1
    $\begingroup$ The Berlekamp et al result is much earlier than that of Vardy! Look at the volume numbers of the IT Transactions. $\endgroup$
    – kodlu
    Sep 23 '21 at 21:53
  • $\begingroup$ @kodlu Thanks for pointing it out. $\endgroup$
    – Root
    Sep 24 '21 at 4:09

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.