Class Id: 8332
Days: TTh
Start Time: 01:30 PM
End Time: 02:50 PM
Building: COMPU
Room: 301
Course Id: 3683
Departments and Numbers: COS 522
Area:
Title: Computational Complexity
Description: 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, l). Definitions of randomness. Pseudorandomness and derandomizations. Lower bounds for concrete models such as algebraic decision trees, bounded-depth circuits, and monotone circuits.
Prerequisites: COS 423
Professors: Sanjeev Arora
Click here to do another class search
Created by Bob Dondero.