MIT 6.840 - Theory of Computation
Taught by Prof. Michael Sipser in Fall 2020.
This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.
Course website Lecture Videos (YouTube)