Some Suggested Topics for Reading
These are just some suggested topics. (You may pick other topics,
if they interest you.) Pointers to specific reading material can be
discussed late on.
- Derandomization/Pseudorandomness (in particular the use of extractors). [See chapters 20 & 21 of the textbook.]
- Complexity of game theoretic problems. [e.g. PPAD completeness (see papers).]
- Computing with real/complex numbers [see a survey.]
- Topological criteria for complexity
- Computational complexity and economics [see a recent paper]
- Topics in Computational Learning theory (and hardness of learning)
- DNA computing
- Impagliazzo's Worlds [see this paper. ]
- Average case hardness [see links.]
- Phase transitions in complexity [e.g. see this book. ]
- Complexity classes related to cryptography [e.g. Statistical ZK]