# A Largish Sum-of-squares Implies Circuit Hardness (and Derandomization)

## Speaker:

Prof. Nitin Saxena

## Affiliation:

Indian Institute of Technology Kanpur
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.