Sum of Squares Lower Bounds for Refuting Any CSP
summary
Proves tight lower bounds showing the Sum‑of‑Squares (SOS) hierarchy cannot refute random CSPs below the specific density thresholds it earlier achieves, matching prior SOS upper bounds up to logs. Construction builds degree‑D pseudodistributions whose local marginals match the best t‑wise uniform witness distributions (the sigma_t(P) values), and checks the PSD constraints to show SOS fails (notably 3‑SAT stays hard until about an n^{1/2} threshold).
AI-written summary · about