Survey Papers

Let's end this week how we started it, with a survey paper. Luca Trevisan has recently posted on ECCC a new survey Some Applications of Coding Theory in Computational Complexity. The survey gives a rather in-depth look at several different types of codes with some connections to private information retrieval, average-case complexity and probabilistically checkable proofs. Trevisan gives a broader and more in-depth look at coding theory than an earlier yet also excellent survey by Madhu Sudan focusing on list decoding.

Survey papers play a valuable role in our field. As computational complexity has broadened over the years, one cannot hope to keep on top of all of the many areas. A survey paper written by an expert in the field can perform many valuable tasks including

• Putting the main results of an area in a common framework. Early work often uses different notation and definitions making it hard to compare one paper to another. Fixing the notation and definitions allow us to easily compare different results. A well-liked survey can also influence future notation.
• Proofs get easier over time and a survey can give easier-to-follow proofs of old results. A survey can also develop a common proof technique useful for many result in the area.
• Giving the author's informed opinion to the importance of different results in an area.
• Stating open problems and directing future research in that area.

In case I've managed to put the survey bug in you, here are two topics where we've seen several recent research papers but lack good surveys that I know of.

1. The complexity of Nash Equilibrium
2. ε-biased Sets