On Semi-Algebraic Proofs and Algorithms
summary
Shows that minimizing conical junta degree on the violations polynomial exactly matches Sherali‑Adams degree via a Hrubeš‑style factorization, uses slack matrices and non-negative rank plus Karchmer‑Wigderson inequalities to connect polytopes to circuits, and lifts conical‑junta lower bounds to separate monotone circuit power from MSEP-1. Constructs an iteration family with linear conical‑junta degree but easy resolution, gives feasible interpolation into monotone separation complexity, and flags the KMR 1/100N loss and weak vs strong MLP gate separation as open problems.
AI-written summary · about