<p>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.</p>

<p>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 <a href="http://infoscience.epfl.ch/record/104417" rel="nofollow">Lorenz Minder's thesis</a>.</p>

<p>Finally, there's a survey on <em>tractable</em> algorithmic problems in coding, including recent developments in list decoding: <a href="http://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf" rel="nofollow">Algorithmic Results in List Decoding</a>. This is a good resource to quickly learn about basics of coding theory. Also for learning the basics, Luca Trevisan's article <a href="http://theory.stanford.edu/~trevisan/pubs/codingsurvey.pdf" rel="nofollow">"Some Applications of Coding Theory in Computational Complexity"</a> may be useful.</p>

CC BY-SA 3.0
2013-02-25T15:30:43.793Z
2013-02-25T15:30:43.793Z
Mahdi Cheraghchi
<p>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.</p>

<p>Are there recent surveys and tutorials of computationally hard problems in coding theory?</p>

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

CC BY-SA 3.0
2014-01-08T02:19:34.793Z
You can see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5962 for a survey.
Pavithran Iyer
<cc.complexity-theory><coding-theory><survey>
Surveys on Algorithmic Problems in Coding Theory
Mohammad Al-Turkistany
# Surveys on Algorithmic Problems in Coding Theory

(Asked by: username_0 on 2013-02-25)

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.

**Tags:** cc.complexity-theory, coding-theory, survey
> **Comments:**
> **username_1**: You can see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5962 for a survey.  

---

## 1 answers

### Answer by username_2 on 2013-02-25. Score: 3

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](http://infoscience.epfl.ch/record/104417).

Finally, there's a survey on *tractable* algorithmic problems in coding, including recent developments in list decoding: [Algorithmic Results in List Decoding](http://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf). 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"](http://theory.stanford.edu/~trevisan/pubs/codingsurvey.pdf) may be useful.


---

