Power and Limits of LP and SDP Relaxations
summary
For any finite valued-CSP language the result gives a precise dichotomy: if the language’s fractional polymorphism support satisfies the bounded width condition then the third-level Sherali–Adams LP solves every instance exactly (a simple polytime algorithm), and otherwise even Θ(n) levels of the Lasserre/Sum-of-Squares SDP fail to solve some instances (hence no polynomial-size SDP captures them). The proof uses fractional polymorphisms, algebraic reductions to linear equation templates, and preserves non‑solvability across those reductions.
AI-written summary · about