Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply \(\text{VP} \neq \text{VNP}\)

For a polynomial f,a weighted sum-of-squares representation (SOS) has the form \(f = \sum_{i\in [s]} c_i f_i^2\) $f={\sum }_{i\in [s]}{c}_i{f}_i^2$ , where the weights \(c_i\) $c_i$ are field elements. The size of the representation is the number of monomials that appear across the \(f_i\) $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) \ge \sqrt d\) $S(f)\ge \sqrt{d}$ .We show that the existence of an explicit univariate polynomial fwith support-sum just slightly larger than the lower bound, that is, \(S(f) \ge d^{0.5+\varepsilon}\) $S(f)\ge d^{0.5+\epsilon }$ , for some \(\varepsilon > 0\) $\epsilon >0$ ,implies that VP \(\ne\) $\ne$ VNP,the major open problem in algebraic complexity.In fact, our proof works for some subconstant functions \(\varepsilon(d) > 0\) $\epsilon (d)>0$ as well.We also consider the sum-of-cubes representation (SOC) of polynomials. We show that an explicit hard polynomialimplies both blackbox-PIT is in P, and VP \(\neq\) $\ne$ VNP.