Skip to main content
Princeton Mobile homeCourses home

Computational Complexity

COS 522/MAT 578

Info tab content
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.
Instructors tab content
Sections tab content

Section L01