Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC1 ≠ VNP

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 =^Psi=1 gi² with each gi d-multilinear. In the case d = 2, Hrubeš, Wigderson and Yehudayoff [13] 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^loglogⁿn), would separate the algebraic complexity classes VNC¹ and VNP.

Duke Scholars

Author Benjamin Rossman Computer Science