Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You can see for a survey. – Pavithran Iyer Jan 8 '14 at 2:19

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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