The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

on YouTube ↗33m

" summary

Shows that low-degree polynomial algorithms (degree ~log N, a class that simulates FIX) provably fail for Random k‑SAT once clause density exceeds a constant times the conjectured algorithmic threshold: no low‑degree polynomial succeeds at density kappa times the predicted ALG value when kappa ≈ 4.9, while OPT sits near 2^K log 2 and ALG is about 2^K log K / K. Proof builds correlated interpolation paths, defines a new overlap entropy forbidden structure (with beta ≈ 3.5), and uses first‑moment calculations plus stability to force a contradiction.

AI-written summary · about

" chapters (8)

1. 0:00Introduction to random k-SAT
2. 1:36Clustering and shattering
3. 3:06Low-degree polynomials
4. 5:47Main results and context
5. 8:11Proof via overlap gap
6. 12:57Ensemble multi-OGP
7. 18:26Defining the forbidden structure
8. 25:03Summary and discussion