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

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée : le cours fournit une introduction claire et rigoureuse aux hypothèses ETH et SETH, avec des démonstrations et des exemples concrets. L’argumentation est solide : chaque résultat est motivé et les preuves sont esquissées. L’enseignant explique les intuitions derrière les réductions et les implications, ce qui permet de comprendre pourquoi ces hypothèses sont centrales en complexité fine-grained. Les exemples choisis (chemin hamiltonien planaire, distance d’édition) illustrent bien les concepts et montrent comment les hypothèses sont utilisées pour dériver des bornes inférieures.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est excellente : le cours est donné par un expert reconnu, les résultats sont présentés avec précision et les preuves sont correctes. Les sources sont implicites (les travaux de Schöning, Impagliazzo, Paturi, etc.) mais le contenu est fiable. L’adéquation titre/contenu est parfaite : le titre annonce exactement le sujet. Aucune publicité n’est présente. Les commentaires ne sont pas fournis, donc aucune analyse des tendances n’est possible.

Le titre décrit précisément le contenu : la leçon porte sur les hypothèses de temps exponentiel (ETH et SETH) et fait partie du cours 'CS Theory Toolkit'.

9/10

Cours universitaire de niveau graduate par un professeur reconnu en informatique théorique, présentant des résultats établis et des preuves rigoureuses. Les hypothèses ETH et SETH sont clairement définies et leurs conséquences sont démontrées. Le contenu est à jour (2020) et les références sont fiables.

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

• 00:00Introduction : passage à la dureté de SAT dans le pire cas.
• 00:30Algorithme de Schöning pour 3-SAT (temps ~1.334^n).
• 03:00Généralisation à k-SAT : temps (2-2/k)^n.
• 05:00Définition de l'ETH (Exponential Time Hypothesis).
• 07:00Exemple : réduction de 3-SAT au chemin hamiltonien planaire, borne inférieure 2^{Ω(√n)}.
• 10:00Conséquences de l'ETH pour des problèmes classiques (Vertex Cover, Clique, Max-Cut).
• 13:00Introduction de la SETH (Strong Exponential Time Hypothesis).
• 15:00Implications de la SETH pour des problèmes polynomiaux (distance d'édition, diamètre).
• 18:00Exemple de Backurs et Indyk : réduction de k-SAT à la distance d'édition.
• 20:00Discussion sur la crédibilité de la SETH et perspectives.

• Page personnelle de Ryan O'Donnell — Page du professeur, mentionnée dans la description comme ressource.
• Page du cours CS Theory Toolkit sur Diderot — Page du cours, mentionnée dans la description.
• Site de Rebecca Kiger (photographe) — Crédit photo de la miniature, mentionné dans la description.

• Exponential time hypothesis (Wikipedia) — Article de synthèse qui confirme les définitions et conséquences de l'ETH et de la SETH.
• Fine-grained complexity (Wikipedia) — Présente le cadre de la complexité fine-grained, dont le cours est une introduction.