syllabus in pdf
less detailed syllabus in html
Office: GDC 4.508
Office Hours: M 3-4, W 2-3
Office Hours: F 11-12, GDC 1.302
|Text:||Michael Sipser, Introduction to the Theory of Computation|
This undergraduate course develops a theoretical framework
to understand computation.
Perhaps the most important concept in the class is that there are
limits to computation.
Some languages are uncomputable; others are "complete"
for certain hard classes, such as NP. Sometimes these
limitations prove useful, as in the case of cryptography. We will
also explore tradeoffs and relationships between different computational
resources, such as time and space.
The course should be similar to the 2016 version.
A list of topics and approximate times follows.
Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
Certificate definition of NL is in Chapter 4 of Arora & Barak's graduate-level textbook Computational Complexity: A Modern Approach.
Winning strategies in two-player games
Complexity of various games and puzzles
Bit commitment overview
Salil Vadhan's course notes on cryptography, including zero knowledge