Essential Hardness: Completing the Exponential Time Hypothesis Proof
Professor of Computer Science
1:22:00·2026·graduate level·Standalone Lecture
This lecture, part of a graduate computational complexity course, delves into the intricate details required to complete the proof of the Exponential Time Hypothesis (ETH).
Theory & AlgosComputational Complexityexponential time hypothesisNP-completenesstheoretical computer science
Lecture 19 in Ryan O'Donnell's Graduate Computational Complexity course at Carnegie Mellon University. First video of the ETH proof: https://www.youtube.com/watch?v=_HlQGMcQWhA
Seminar notes & discussion
No public seminar notes on this lecture yet.