CS6840 Modern Complexity Theory
Feb - May 2021
Coordinates
- Where: Online
- When: J slot (Mon: 17 - 17.50; Wed: 14 - 15.15; Thu: 15.30 - 16.45)
Objectives
This course continues from CS6014 - Computability and Complexity, as we explore more recent topics in complexity theory.
Contents
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
References
[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.
Grading policy
Assignments: 40% (best 4/5)
Scribing: 10%
Course reading: 20%
Mid-sem: 10%
End-sem + viva: 20%
Important dates
Problem Sets (deadlines): Feb 28, Mar 14, Apr 11, Apr 25, May 9
Mid-sem: Mar 25
End-sem: May 13