CSE 201A. Advanced Complexity (4 units)
Link to catalog page: https://catalog.ucsd.edu/courses/CSE.html#cse201a
Description
Polynomial-time hierarchy (PH), BPP in second level of PH, Savitch’s theorem, NL=coNL, nonuniform and circuit complexity, some circuit lower bounds, IP=PSPACE, probabilistic proof checking (PCP), application of PCP to approximation hardness, complexity of proof systems, parallel complexity classes NC and AC, P-completeness. Recommended preparation: CSE 200. Prerequisites: graduate standing.
Prerequisite courses
CSE 201A has no prerequisite courses.
Successor courses
No courses have CSE 201A as a prerequisite.