Quick links

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
Follow us: Facebook Twitter Linkedin