A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
summary
If an explicit univariate family has support sum ≥ D^{1/2+ε} then VP ≠ VNP; a constant ε yields an exponential separation. The proof uses depth reduction, unfolding to a layered branching program and a sum‑of‑squares composition that enforces a degree bound D/2 on summands, converts to multivariate via base‑K substitution, and applies combinatorial monomial counts to contradict small circuits. A stronger sum‑of‑cubes hardness assumption even yields derandomize PIT (polynomial‑time identity testing).
AI-written summary · about