Complexity Theory

Prerequisites: Prerequisites: CS330. - CASCS 332 is recommended. Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems.