Abstract: We study the sum of squares (*SOS*) representation of polynomials, i.e. f = \sum_{i\in s} c_i f_i^2 , where c_i are field elements and f_i(x_1,\ldots,x_n) are polynomials. We are interested in `measuring' the number of monomials that appear across f_i's; call this *support-sum* S(f). Let the degree of f be d and, for simplicity of exposition, fix n=1. We conjecture: For some *explicit* f and some constant \epsilon > 1/2, S(f) \ge d^\epsilon. We prove that the conjecture implies VP\ne VNP (& blackbox-PIT in QuasiP). A more sophisticated version of the conjecture, for sum-of-cubes representation, implies blackbox-PIT is in P.
Note that S(f) \ge d^{1/2} is trivially achieved. So, compared to this, a marginally better lower bound in the SOS suffices to solve the major questions of algebraic complexity. The *SOS-conjecture* is largely field independent, and is itself supported by a dimension-based fact: It holds for a `randomly chosen' degree-d polynomial f(x).
This is ongoing work with Pranjal Dutta (CMI/IITK) and Thomas Thierauf (Ulm/Aalen).
