Seminar Information

Instructors: Balasubramanian A. R., Debarghya Ghoshdastidar 

Format

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.

Assessment

• 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