Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
