Advanced Complexity Theory (Master seminar)

Seminar Information

Instructors: Balasubramanian A. R., Debarghya Ghoshdastidar 


This seminar will cover some of the advanced topics in complexity theory, as well as some related topics in algorithms. 

Each participant will be allotted a topic. The participant will have to deliver a 90-min lecture on the topic. If the lecture is delivered using slides, then the slides must be submitted. If the lecture is given using board, then a detailed lecture note must be submitted. In addition, each participant needs to design one problem based on the lecture, and submit a sample solution.

Pre-requisite: The participants require knowledge of Complexity Theory (IN2003 or equivalent) to participate in this course.

Potential topics

  • PCP theorem and Fourier transform
  • Quantum complexity theory
  • Complexity of counting 
  • Pseudorandom constructions and Expander
  • Sum-of-squares hierarchy
  • Parametrised complexity
  • Fine-grained complexity
  • Circuit lower bounds

References for the topics will be provided during topic selection. In addition, the participants may also propose topics. In this case, please contact the instructors.


  • Delivered lecture and slides/notes (70 points),
  • Design of 1 problem + solution (10 points)
  • Oral examination after lecture (20 points).

In addition, bonus (upto 10 points) can be obtained solving 2 questions designed by others. Submission deadline in February 2022.

Tentative plan

  • Date of de-registration: Beginning of December, 2021
  • Final presentations: In January 2022 and early February 2022 (weekly, Thursdays 16:15-17:45)

Office hours: weekly Thursdays 16:15-17:45, from the beginning of the semester