Syllabus
- Randomness and pseudorandom generators.
- Communication complexity and interactive protocols.
- Error-correcting codes and their applications in complexity.
- Lower bounds.
- Expanders and their applications.
Annotation
This course covers advanced topics in computational complexity. Each semester will be devoted to a different topic.
Topics will include among others: randomness and pseudorandom generators, communication complexity and interactive protocols, error-correcting codes and their applications in complexity, lower bounds, expanders and their applications. The course is intended to students from upper classes and to graduate students.
Prerequisites: understanding of elementary concepts from computational complexity, probability theory and discrete math.