2026-07-22T04:46:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25400 2026-03-19T13:04:32Z ddc:004 open_access

Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP Rossman, Benjamin Zhu, Davidson sum-of-squares arithmetic formulas The sum-of-squares (SoS) complexity of a d-multiquadratic polynomial f (quadratic in each of d blocks of n variables) is the minimum s such that f = ∑_{i = 1}^s g_i² with each g_i d-multilinear. In the case d = 2, Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011] showed that an n^{1+Ω(1)} lower bound on the SoS complexity of explicit biquadratic polynomials implies an exponential lower bound for non-commutative arithmetic circuits. In this paper, we establish an analogous connection between general multiquadratic sum-of-squares and commutative arithmetic formulas. Specifically, we show that an n^{d-o(log d)} lower bound on the SoS complexity of explicit d-multiquadratic polynomials, for any d = d(n) with ω(1) ≤ d(n) ≤ O((log n)/(log log n)), would separate the algebraic complexity classes VNC¹ and VNP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Rossman and Davidson Zhu 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.113 urn:nbn:de:0030-drops-254006 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.113 eng https://creativecommons.org/licenses/by/4.0/legalcode