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

For a polynomial f , a weighted sum-of-squares representation (SOS) has the form f = ∑i∈ [s] 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) ≥ d0.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 ≠ ≠ .