Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

on YouTube ↗39m

" summary

Proves a lifting theorem: for the inner-product gadget with B ≳ c log n the non-negative rank of a pattern matrix Mf is at least exp(Ω(B · degree-plus(f))) (degree-plus = fewest variables per nonnegative summand), and this forces sub-exponential LP size to beat the trivial 7/8 (Max‑3SAT) or 1/2 (Max‑Cut) thresholds by any constant ε. Main tools are non-negative rank of pattern matrices, a greedy decomposition into aligned blockwise-dense sources, and the inner‑product two‑source extractor to convert high‑entropy factors into small-degree-plus certificates.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 2:19Linear Programs vs CSPs
3. 4:35Arbitrary LPs for CSPs?
4. 5:34Example: Max-Cut
5. 8:18Outline
6. 8:48Pattern Matrices
7. 10:25Pattern Matrix View
8. 11:39Lifting Non-Negative Rank
9. 19:21NNR and Rectangles
10. 24:47Min-Entropy Thumb rule: Small non-negative rank
11. 31:22Proof Sketch Algorithm: X - Y
12. 33:42Summary