Consequences of SETH: Tight Bounds for Some More Problems

on YouTube ↗49m

" summary

Examines implications of the Strong Exponential Time Hypothesis (SETH) for getting tight time lower bounds on several computational problems; identifies specific problems for which SETH implies no faster algorithms than known, and explains the reductions or conditional comparisons used to derive those tight bounds.

AI-written summary · about

" chapters (23)

1. 0:00Intro
2. 0:24Tight lower bounds
3. 2:00Strong ETH
4. 3:00Showing Lower Bounds under SETH
5. 5:43SAT → k-Dominating Set Variables
6. 8:45SAT → k-Dominating Set analysis
7. 11:00Dominating Set, wrapping up
8. 15:38Independent Sets on an Even Path
9. 17:14d-SAT S Independent Set proof by example
10. 18:11Independent Sets - Assignments
11. 19:33Dealing with true false
12. 21:07Treewidth Bound by picture
13. 22:45Independent Set / Treewidth wrap up
14. 24:123t lower bound for Dominating Set?
15. 26:56Hitting Set/n
16. 31:52Some deep math
17. 33:36d-SAT Hitting Set Group the variables into groups of size g, and set
18. 35:05Forcing solution [1/2] vertices in a group?
19. 36:11Analyzing a group
20. 38:11Forbidding partial assignments
21. 39:58Satisfying Assignments Hitting Sets
22. 41:12Important Open Problems
23. 46:48Conclusions