Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory Toolkit

Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 July 17, 2020 ⏱ 23 min 👁 1K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

ETHSETHfine-grained complexitySATNP-hardness

Summary

This lecture from CMU’s CS Theory Toolkit, taught by Ryan O’Donnell, introduces the Exponential Time Hypothesis (ETH) and the Strong Exponential Time Hypothesis (SETH). ETH posits that 3-SAT cannot be solved in subexponential time, i.e., it requires 2^δn for some δ>0. SETH strengthens this, asserting that for any ε>0, there exists a k such that k-SAT requires time 2^(1-ε)n. The lecture explains the motivation behind these hypotheses, their implications for NP-hard problems, and their use in fine-grained complexity. It discusses algorithms for SAT, such as the Schöning algorithm for k-SAT, and shows how ETH implies lower bounds for problems like planar Hamiltonian path (2^Ω(√n)) and vertex cover (no subexponential in k). SETH is used to prove tight lower bounds for problems in P, such as edit distance (no O(n^(2-ε)) algorithm) and graph diameter (no O(mn^(1-ε))). The lecture emphasizes the importance of efficient reductions and the distinction between ETH and SETH. It concludes with examples of fine-grained complexity results, including all-pairs max flow and subset sum, demonstrating the power of these hypotheses in establishing precise algorithmic lower bounds.

177 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a high-value overview of ETH and SETH, explaining their definitions, motivations, and applications. The argumentation is solid, with clear logical progression from the basic definitions to their consequences. The lecturer uses concrete examples (planar Hamiltonian path, edit distance) to illustrate how these hypotheses yield lower bounds. The reasoning is rigorous, and the lecturer emphasizes the importance of reduction efficiency. The presentation is well-structured, making complex concepts accessible to a graduate-level audience.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, presenting established results from the literature. The lecturer cites key works (e.g., Impagliazzo & Paturi for ETH, Calabro et al. for SETH, Backurs & Indyk for edit distance) and explains their significance. The title accurately reflects the content. The description provides links to the lecturer’s homepage and course materials, which are relevant resources. No external sources are cited beyond these, but the lecture itself is based on peer-reviewed research.

163 words

Title / Content Match

The title accurately reflects the content: the lecture covers the Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH) in depth.

Quality & Reliability

8/10

Lecture by a recognized expert (Ryan O'Donnell, CMU professor) in theoretical computer science, part of a graduate course. The content is rigorous, well-structured, and based on established research (ETH, SETH, fine-grained complexity). No obvious errors or unsupported claims. The presentation is clear and includes proofs and examples.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

This lecture provides a clear and concise introduction to ETH and SETH, explaining their role in fine-grained complexity. It highlights how these hypotheses yield tight lower bounds for problems in P, such as edit distance and graph diameter, which is a relatively recent development. The lecture emphasizes the importance of efficient reductions and the distinction between ETH and SETH.

Pour aller plus loin :

102 words

Radar Profile

The radar profile shows high scores in technical level and information quality, with slightly lower but still strong scores in quantity and reliability. This indicates a technically dense lecture with accurate content, suitable for a graduate-level audience.

Reliability 8/10