Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory Toolkit
NP ≠ P tells us that k-SAT is not in polynomial time, but just how much non-polynomial time does it take? This is the subject of the ETH (Exponential Time Hypothesis) and SETH (Strong Exponential Time Hypothesis). Lecture 26d of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture:
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (https://www.rebeccakphoto.com/)