CS 170: Efficient Algorithms and Intractable Problems
Luca Trevisan
Learn efficient algorithms and tackle intractable problems with Luca Trevisan's CS 170 complexity theory course. Explore fundamental computer science concepts.
More resources on Complexity Theory
Scott Aaronson's Blog
Shtetl-Optimized, written by quantum computing theorist Scott Aaronson, posts long arguments about P versus NP, quantum supremacy claims, and open problems. Readers gain a working sense of how complexity researchers actually debate results.
Complexity Zoo
Wiki catalogue of over five hundred computational complexity classes, each with a formal definition, known inclusions and references. Useful for checking what a class such as BPP or PH means and how it relates to others.
Theory of Computation (MIT 18.404J)
Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study.
Advanced Topics in Cryptography (MIT 6.5630)
Research-level study of proof systems: interactive proofs, multi-prover interactive proofs and probabilistically checkable proofs, then how cryptography turns them into succinct non-interactive arguments (SNARGs). 17 lecture videos prepare learners to read current work on delegation and verifiable computation.
NandGame
A browser puzzle that starts with a single NAND gate and has you compose latches, adders, an ALU, memory, and finally a working CPU with its own assembler and instruction set.
Introduction to the Theory of Computation (3rd Edition)
Sipser's standard text builds automata, Turing machines, decidability, reducibility, Rice-style arguments and complexity from careful definitions and complete proofs. After it you can prove a problem undecidable by reduction and state the Church-Turing thesis precisely.