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

Course Materials

Moodle
Lectures and references
Problem Sets: 1, 2, 3, 4