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.

- The complexity of Nash Equilibrium
- ε-biased Sets

Hmm, it appears my summer reading list has just grown by 50-so pages. In ways I treat the Knuth books as giant surveys; but they aren't very good for learning algorithm design and they serve more as a reference too. (If only the best of Knuth and CLR could be turned into a considerable algorithm encyclopedia.)

ReplyDelete