Feb - May 2021
- Where: Online
- When: J slot (Mon: 17 - 17.50; Wed: 14 - 15.15; Thu: 15.30 - 16.45)
This course continues from CS6014 - Computability and Complexity, as we explore more recent topics in complexity theory.
The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.
- Complexity of counting problems
- Non-uniform models and circuit complexity
- BPP vs P - Hardness vs Randomness
- Interactive Proofs and PCPs
[K]: Theory of Computation - Dexter C. Kozen
[AB]: Computational Complexity: A Modern Approach - Sanjeev Arora and Boaz Barak
[DK]: Theory of Computational Complexity - Ding-Zhu Du and Ker-I Ko
There are a large number of lecture notes and resources available online, which we will refer to during the course.
Assignments: 40% (best 4/5)
Course reading: 20%
End-sem + viva: 20%
Problem Sets (deadlines): Feb 28, Mar 14, Apr 11, Apr 25, May 9
Mid-sem: Mar 25
End-sem: May 13