This course covers advanced topics in computational complexity. It studies the effect of non-traditional resources, such as randomness, non-determinism, alternation, and counting on our ability to compute: Which problems become easier with such resources, and which ones remain intractable? And what tradeoffs are possible among these resources? Specific themes include:
- Review of time and space complexity.
- Non-determinism and alternation.
- Non-uniform models of computation and lower bounds.
- Interaction, proof, and knowledge.
- Probabilistic Proof Systems