| Title | : | A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization |
| Speaker | : | Pranjal Dutta (CMI & IIT Kanpur) |
| Details | : | Tue, Sep 22, 2020 4:00 PM, @ Google Meet |
| Abstract | : | For a polynomial f, we study the sum-of-squares representation (SOS), i.e.f = c_1*f_1^2 + ... + c_s*f_s^2, where c_i are field elements and the f_i are polynomials. The size of the representation is the number of monomials that appear across the polynomials f_i. Its minimum is the support-sum S(f) of f. For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of a full-support univariate polynomial, f of degree d is S(f) >= d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) >= d^{0.5+varepsilon(d)}, for a sub-constant function varepsilon(d)>omega(sqrt{loglog d/log d}), implies that VP is different from VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Theta(d). We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P. This is based on joint work with Prof. Nitin Saxena (CSE, IIT Kanpur) and Prof. Thomas Thierauf (Aalen University). The full version of the paper is available here. |