Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates
summary
Shows that starting from any worst-case clause hypergraph and flipping each literal with small constant probability (e.g. 0.01) yields the same density–time refutation tradeoff as fully random CSPs: the smoothed model admits polynomial refutation at densities around N^{k/2} and the same interpolation of running time vs density via a parameter L. Key steps are reduction to semi-random k‑XOR, analysis with Kikuchi matrices and a spectral double counting (trace‑method) argument, and a proof of Feige’s hypergraph girth conjecture up to polylog factors, which supplies polynomial‑size certificates.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 6:41Refutation algorithm
- 8:29State of knowledge
- 13:41Complexity
- 14:42Smooth CSP Model
- 15:28Algorithmic Result
- 18:32Certificates
- 19:59Graphs
- 26:01Proof
- 30:40The Plan
- 41:36Proofs
- 45:49Trace Method
related talks
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
46mPhase Transitions in Random CSPs
48mUnstructured Hardness to Average-Case Randomness
41mCounting Solutions to Random CNF Formulas
48mProvable Robustness Beyond Bound Propagation
52mMax Cut with Linear Programs: Sherali-Adams Strikes Back
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 00mAverage-case Complexity for Polynomials, and All That