Prerequisite

Basic complexity (the classes P, NP, BPP), basic probability.
This is a graduate course, where undergrads are encouraged to take 0369.3049.
In some special cases, however, undergrads who got my personal permission can take the course.