Instructor: Otis Jennings
Description coming soon!
Instructor: Ben Rossman
This course is an advanced undergraduate-level introduction to Computational Complexity Theory. Starting out with the basics of Turing machines and computability, we will cover fundamental notions including NP-completeness, time and space complexity, circuit models of computation, and the power of randomness. The main text will be Sipser’s “Introduction to the Theory of Computing” (Parts II and III). Recommended prerequisites: Compsci 230 and 330, or equivalent background in discrete math and some basic analysis of algorithms.
Department of Mathematics