Advanced Complexity

4 credits

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.