3
$\begingroup$

Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. I'm aware of the NP-completeness of Maximum likelihood decoding problem.

Are there recent surveys and tutorials of computationally hard problems in coding theory?

I'm more interested in surveys that do not assume strong background in coding theory.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

There are known worst-case hardness results about ML decoding (for general and specific families of codes such as Reed-Solomon), computing or approximating minimum distance of codes, and so on. However there is a great room for improvement in these directions and several seemingly intractable problems are not analyzed yet.

There are coding theoretic problems that are conjectured to be intractable, such as problems related to decoding random ensembles of codes. Such intractability assumptions are related to hardness of learning noisy parities and also form the basis of coding-theoretic public key cryptography (which is a big area of research by itself). For a good account of the latter, see Lorenz Minder's thesis.

Finally, there's a survey on tractable algorithmic problems in coding, including recent developments in list decoding: Algorithmic Results in List Decoding. This is a good resource to quickly learn about basics of coding theory. Also for learning the basics, Luca Trevisan's article "Some Applications of Coding Theory in Computational Complexity" may be useful.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.