COS 522: Computational Complexity
Introduction to research in computational complexity theory. Computational models: nondeterministic, alternating, and probabilistic machines. Boolean circuits. Complexity classes associated with these models: NP, Polynomial hierarchy, BPP, P/poly, etc. Complete problems. Interactive proof systems and probabilistically checkable proofs: IP=PSPACE and NP=PCP (log n, 1). Definitions of randomness. Pseudorandomness and derandomizations. Lower bounds for concrete models such as algebraic decision trees, bounded-depth circuits, and monotone circuits.
Semester:
Spring23
Lectures:
Tuesday,Thursday, 3:00-4:20
Location:
Friend Center 004
Faculty
Gillat Kol
Office:
Computer Science 316
Extension:
5386
Email:
gkol
Additional Information
The Graduate Coordinator is Nicki Mahler
Email:
ngotsis
Office:
Computer Science 213
Extension:
5387