Consequences of ETH: Tight Bounds for Various Problems
summary
Examines implications of the Exponential Time Hypothesis (ETH) for algorithmic lower bounds, deriving tight time complexity bounds for a range of problems by reducing from ETH-based hard problems and analyzing parameterized and exact algorithms. Focuses on concrete problem classes and how ETH limits possible improvements in their running times.
AI-written summary · about
chapters (13)
- 0:00Start
- 8:02Lower bounds based on ETH
- 11:05Lower bounds for planar problems
- 13:00Treewidth
- 30:08Lower bound on the exponent
- 32:54Tight bounds
- 39:30ODD SET
- 45:16GRID TILING and planar problems
- 45:32A classical problem
- 49:56Putting together the gadgets
- 52:40Reduction to unit disks
- 54:16Center-pivot irrigation
- 55:42Higher dimensions
related talks
23mTowards General and Tight Hardness Results for Graph Problems
25mLower Bounds for Problems Parameterized by Clique-width
19mThe Time Complexity of Consensus Under Oblivious Message Adversaries
29mAn Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
01h 21mComputational Complexity in Theory and in Practice
29mEquality, Revisited
29mAmplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers
45mOn Analyzing Blockchain Consistency