On the Usefulness of the Strong Exponential Time Hypothesis
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Argues Strong Exponential Time Hypothesis is likely false while conceding uncertainty, and shows that chasing that refutation yields concrete results: exponential-time reductions from SAT to Orthogonal Vectors give tight quadratic hardness, a Merlin–Arthur protocol counts solutions in 2^{n/2} time with 2^{n/2}-bit proofs, algebraic reductions to polynomials produce ACC circuit SAT algorithms that break previous barriers and imply NEXP not in ACC0, and polynomial tricks lead to faster APSP: n^3 / 2^{sqrt(log n)} time.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:50Notation
- 7:59Whats the point
- 10:00How did you get into this
- 12:50End of Omega Time
- 15:30Solving Sat Faster
- 18:42Results
- 25:39Another Approach
- 31:06Constant Depth
- 33:02Representation Theorem
- 35:13Another Seth Attack
- 36:43All Pairs shortest paths
- 41:31The Nondeterministic Set
- 45:12Is Seth True
- 46:24Strengthening Seth
- 54:42Proof of seth