Computational Complexity

Computational complexity theory is a mathematical discipline that studies efficient computation. The course covers some of the truly beautiful ideas of modern complexity theory such as: approaches to the famous P vs NP question and why they are stuck; complexity classes and their relationship; circuit lower bounds; proof systems such as zero knowledge proofs, interactive proofs and probabilistically checkable proofs; hardness of approximation; de-randomization and the hardness vs randomness paradigm; quantum computing.