Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reduc

on YouTube ↗59m

" summary

Introduces a non-deterministic strong ETH variant and proves concrete non-reducibility: max flow and min-cost max flow admit linear-time nondeterministic and co-nondeterministic verifiers (so no deterministic fine-grained reduction from SETH above O(m)), 3SUM gets a nondet/co-nondet listing+counting algorithm running in about n^{3/2} time by working modulo a carefully chosen prime, and APSP reduces to zero-weight triangle counted via polynomial entries (matrix mult exponent) yielding ~n^{2.69} bounds; falsity of the new hypothesis implies new circuit lower bounds.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 0:32Fine-Grained Hardness
3. 3:58Important conjectures: All-Pairs Shortest Path
4. 4:28Important conjectures: Strong Exponential Time Hypothesis
5. 5:27Conditional Lower Bounds
6. 12:21Property X
7. 16:42Outline
8. 17:37SETH and NSETH Imply Circuit Lower Bounds
9. 18:54SETH and NSETH are Algorithmic
10. 23:43Min-Cost Maximum Flow Problem
11. 25:14Certifying Negative Cycles
12. 27:233-Sum problem
13. 28:27List and Count Algorithm for 3-SUM
14. 36:35List and Count Algorithm for ZWI
15. 37:52Counting Solutions
16. 39:13Analysis
17. 41:49Quantifier Structures of Hard Problems
18. 48:57Example: Hitting Set
19. 50:30Randomized Reductions
20. 54:33Summary
21. 55:13Open Questions