Course description
This is an introductory graduate level course to the theory of computation. We will focus on the fundamental mathematical model of a Turing Machine, discuss its powers and limitations, discuss computational resources that a TM might use (time, space, randomness) and the complexity classes associated with them (P, NP, PSPACE, BPP, RP, etc). In the latter part of the course we'll cover more advanced topics, possibly including Interactive Proofs (IP, PCP).
Prerequisites: A course on discrete math and undergraduate algorithms.