Other Topics
Additional (more advanced or specialized) topics will be introduced
in the rest of this course.
Lecture #20: Lower Bounds for Structured Models — Decision Trees,
and Information-Theoretic and Adversarial Lower Bounds
Lecture #21: Boolean Decision Trees
Activity #9: Lower Bounds for Structured Models of Computation
Lecture #22: Interactive Proofs
Lecture #23: Approximation Algorithms, the PCP Theorem, and the
Hardness of Approximation
Activity #10: Interactive Proofs
Lecture #24: Communication Complexity
Activity #11: Communication Complexity
