Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP VNP

Abstract For a polynomial f, a weighted sum-of-squares representation (SOS) has the form f = ₈ ₒ cᵢ fᵢ² f = ∑ i ∈ s c i f i 2, where the weights cᵢ c i are field elements. The size of the representation is the number of monomials that appear across the fᵢ f i 's. Its minimum across all such decompositions is called the support-sum S (f) of f. For a univariate polynomial f of degree d of full support, a lower bound for the support-sum is S (f) d S (f) ≥ d. We show that the existence of an explicit univariate polynomial f with support-sum just slightly larger than the lower bound, that is, S (f) d^0. 5+ S (f) ≥ d 0. 5 + ε, for some > 0 ε > 0, implies that ≠, the major open problem in algebraic complexity. In fact, our proof works for some subconstant functions (d) > 0 ε (d) > 0 as well. We also consider the sum-of-cubes representation (SOC) of polynomials. We show that an explicit hard polynomial implies both blackbox-PIT is in, and ≠.