Prerona Chatterjee

Introduction to Complexity Theory (CS453 and CS631)

• Introductory course for advanced undergraduate and new graduate students.
• Class Timings: Mondays and Wednesdays from 17:30 to 19:00.
• Location: Room M2 at NISER Bhubaneswar
• Lecture Notes: Link (Please send me an email for viewing permission.)

 

References

• Introduction to Theoretical Computer Science (Barak)
• Introduction to the Theory of Computation (Michael Sipser)
• Computational Complexity - A Modern Approach. (Sanjeev Arora, Boaz Barak)

 

Grading

• Weekly Quiz (Tuesdays from 17:45 to 18:30) - 20%
• Assignments (take-home) - 20%
• Mid-sem (in-class) - 20%
• End-sem (in-class) - 40%

 

Problem Sets

• Quiz 1
• Quiz 2
• Quiz 3
• Assignment 1
• Quiz 4
• Quiz 4

 

Lecture Summary

Week 1: Defining Computation via Circuits, Universality of Circuits, the class SIZE{n,m}(s)

• Lecture 0 (5th Jan, 2026): Administrative details and introduction to the course.
• Lecture 1 (6th Jan, 2026): Defining Circuits, Universality of Circuits.
• Lecture 2 (7th Jan, 2026): Simple operations like addition, multiplication and if-then conditions as circuits, the class SIZE{n,m}(s).

Week 2: Circuits as strings & inputs to circuits, Existence of Hard Functions, Size Hierarchy Theorem

• Lecture 3 (12th Jan, 2026): Circuits as strings, Existence of hard functions, boolean functions as polynomials.
• Lecture 4 (14th Jan, 2026): Existence of a Universal Circuit, Size Hierarchy Theorem.

Week 3: Turing Machines, Turing Machines as Programs, RAM Model, Church-Turing Thesis

• Lecture 5 (19th Jan, 2026): Uniform Computation, Defining Turing Machines.
• Lecture 6 (21st Jan, 2026): Configurations of a Turing Machine, Turing Machines as Programs, RAM Model, Church Turing Thesis.

Week 4: Uncomputability, Defining Time Complexity, P and EXP

• Lecture 7 (28th Jan, 2026): Universal TMs, Uncomputability, Halting Problem, the class TIME(t(n)), P and EXP

Week 5: Hierarchy Theorems, Non-Uniform Computation vs Uniform Computation, NP, NP-Completeness

• Lecture 8 (2nd Feb, 2026): Time Hierarchy Theorem, Non-Uniform Computation, the class SIZE(s(n)), P/poly, P vs P/poly, Defining k-SAT, 2-SAT is in P.
• Lecture 9 (4th Feb, 2026): Defining NP, Non-Deterministic Turing Machines, Defining NTIME(t(n)), N-Time Hierarchy Theorem, Poly-time Reductions, NP-Completeness.

Week 6: Cook-Levin Theorem, Ladner's Theorem

• Lecture 10 (10th Feb, 2026): Cook-Levin Theorem
• Lecture 11 (12th Feb, 2026): Ladner's Theorem.

Week 7: Oracle Turing Machines, Baker-Gill-Solovay Theorem, coNP, Polynomial Hierarchy

• Lecture 12 (16th Feb, 2026): Oracle Turing Machines, Baker-Gill-Solovay Theorem.
• Lecture 13 (18th Feb, 2026): coNP, Polynomial Hierarchy, TQBF, Collapse of PH if P=NP.

Week 8: Circuit Classes, Karp-Lipton Theorem

Week 9: Defining Space Complexity, Space Hierarchy Theorem, Savitch's Theorem, the class PSPACE and its relation with NP

Week 10: The classes L and NL, log space reductions, NL completeness

Week 11: Randomised Computation, Efficient Randomised Algorithms for Polynomial Identity Testing, Bipartite Matching

Week 12: Modelling Randomised Computation, the class BPP, Upperbounds for BPP

Week 13: Derandomisation and PRGs

Weeks 14: Interactive Proofs