2
$\begingroup$

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?

Thanks!

$\endgroup$
  • 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$ – Sasho Nikolov Nov 16 '19 at 10:27

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.