Computational Complexity (M.Tech CS, 2022-23)

Instructors Sourav Chakraborty and Arijit Ghosh

Status Completed

Description Introduction to Computational Complexity Theory

Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences

Class timings Mondays and Wednesdays from 2:30 pm - 4:15 pm

Syllabus

• NP and NP-Completeness 

• Diagonalization

• Space complexity 

• Polynomial hierarchy

• Alternations

• Boolean circuits

• Randomized computations

• Interactive proofs

• PCP Theorem and hardness of approximation

• Communication complexity

References

• [AB09] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

• [MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2017.

• [MR95] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.