I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance.

I of course found that calculating the distance in exact is NP-Hard and that even Approximate it to any constant factor is hard (under randomized reductions).

However, this result is a bit old, and I didn't manage to find any newer hardness of approximation result.

I also didn't manage to find any polynomial approximation algorithms to this problem (for any factor) - all the works I found are either deal with specific code families or even don't relate to a promised gap approximation and bring only huristic/paractical result as a proof to the algorithm worthyness

Did my search miss something? Is there any current work that relates to this problem for a gap between constant and the trivial linear gap, and proves inapproximability /shows approximation for this gap?


  • 2
    $\begingroup$ Maybe @NoahStephens-Davidowitz can help here. This recent paper contains some new hardness results for MDP, and references to older work. For example, it is known that no $2^{(\log n)^{1-\varepsilon}}$ factor approximation is possible unless NP is contained in quasi-polynomial time (see, e.g., arxiv.org/pdf/1010.1481.pdf). $\endgroup$ Commented Nov 16, 2019 at 10:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.