Computational Complexity

Computational complexity theory is a mathematical discipline that explores the boundaries of efficient computation. This course introduces some of the most engaging ideas in complexity theory, showcasing how advanced mathematical methods can address profound philosophical questions. We explore the significance of the P vs NP problem, analyzing approaches like diagonalization and circuit lower bounds, while also examining why progress has been slow. Topics include proof systems such as zero-knowledge proofs, interactive proofs, and probabilistically checkable proofs