2026-07-22T21:35:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13562 2024-03-12T11:59:46Z ddc:004 open_access

A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization Dutta, Pranjal Saxena, Nitin Thierauf, Thomas VP VNP hitting set circuit polynomial sparsity SOS SOC PIT lower bound For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. 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+ε(d)}, for a sub-constant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ 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) = Θ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranjal Dutta and Nitin Saxena and Thomas Thierauf 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.23 urn:nbn:de:0030-drops-135629 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.23 eng https://creativecommons.org/licenses/by/3.0/legalcode