CSE 201AAdvanced Complexity
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
From the catalog: “graduate standing.”