Computer Science
CS 7805: Complexity Theory
Lecture - 4 credits
ND
EI
IC
FQ
SI
AD
DD
ER
WF
WD
WI
EX
CE
- Covers core topics in computational complexity, including NP-completeness, time and space complexity, polynomial hierarchy, circuit complexity, probabilistic computation, interactive proofs, and hardness of approximation.
- Moves to more advanced topics that may include lower bounds, pseudorandomness, cryptography, and communication complexity.
Covers core topics in computational complexity, including NP-completeness, time and space complexity, polynomial hierarchy, circuit complexity, probabilistic computation, interactive proofs, and hardness of approximation. Show more.
Pre-requisites