Harvard University homepage
HARVARD.EDU

Madhu Sudan: Harvard CS 221: Computational Complexity (Spring 2018) – Course announcement

Prereq: CS 121 + Mathematical Maturity
Time: Tu-Th 1:00pm – 2:30pm
Location: MD 221
Harvard CS 221: Computational Complexity (Spring 2018) homepage

This course covers advanced topics in computational complexity. It studies the effect of non-traditional resources, such as randomness, non-determinism, alternation, and counting on our ability to compute: Which problems become easier with such resources, and which ones remain intractable? And what tradeoffs are possible among these resources? Specific themes include:

  • Review of time and space complexity.
  • Non-determinism and alternation.
  • Non-uniform models of computation and lower bounds.
  • Interaction, proof, and knowledge.
  • Probabilistic Proof Systems

Other current topics may be covered depending on time and interest. A tentative list of topics by lecture is available at the course website. If you are interested (even tentatively) in the course, please sign up on the piazza site (https://piazza.com/harvard/spring2018/cs221/home).

Instructor: Madhu Sudan
TF: Preetum Nakkiran