The Exponential Time Hypothesis: Foundations of Computational Hardness
Professor of Computer Science
1:19:45·2026·graduate level·Standalone Lecture
An foundational lecture introducing the Exponential Time Hypothesis (ETH), a crucial conjecture in theoretical computer science that posits limits on efficient solvability for NP-hard problems.
Theory & AlgosComputational Complexityexponential time hypothesisNP-completenesstheoretical computer science
Lecture 18 in Ryan O'Donnell's Graduate Computational Complexity course at Carnegie Mellon University.
Comments
Add a comment...Sign in