   ISSN 1088-6834(online) ISSN 0894-0347(print)

Non-commutative circuits and the sum-of-squares problem

Authors: Pavel Hrubeš, Avi Wigderson and Amir Yehudayoff
Journal: J. Amer. Math. Soc. 24 (2011), 871-898
MSC (2010): Primary 03D15, 68Q17; Secondary 11E25
DOI: https://doi.org/10.1090/S0894-0347-2011-00694-2
Published electronically: February 2, 2011
MathSciNet review: 2784331
Full-text PDF Free Access

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree-four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that there exists an identity \begin{equation*} (0.1)\quad \quad (x_1^2+x_2^2+\cdots + x_k^2)\cdot (y_1^2+y_2^2+\cdots + y_k^2)= f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} , \quad \quad \end{equation*} where each $f_{i} = f_i(X,Y)$ is a bilinear form in $X=\{x_{1},\dots ,x_{k}\}$ and $Y=\{y_{1},\dots , y_{k}\}$. Over the complex numbers, we show that a sufficiently strong superlinear lower bound on $n$ in (0.1), namely, $n\geq k^{1+\epsilon }$ with $\epsilon >0$, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

More generally, we consider such sum-of-squares identities for any biqua- dratic polynomial $h(X,Y)$, namely \begin{equation*} (0.2) \quad \quad \qquad \quad \quad \quad \quad h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} . \quad \quad \qquad \quad \quad \quad \quad \end{equation*} Again, proving $n\geq k^{1+\epsilon }$ in (0.2) for any explicit $h$ over the complex numbers gives an exponential lower bound for the non-commutative permanent. Our proofs rely on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of Valiant’s completeness of the permanent.

We prove such a superlinear bound in one special case. Over the real numbers, we construct an explicit biquadratic polynomial $h$ such that $n$ in (0.2) must be at least $\Omega (k^{2})$. Unfortunately, this result does not imply circuit lower bounds. We also present other structural results about non-commutative arithmetic circuits. We show that any non-commutative circuit computing an ordered non-commutative polynomial can be efficiently transformed to a syntactically multilinear circuit computing that polynomial. The permanent, for example, is ordered. Hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds. We also prove an exponential lower bound on the size of a non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.

[Enhancements On Off] (What's this?)

References

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 03D15, 68Q17, 11E25

Retrieve articles in all journals with MSC (2010): 03D15, 68Q17, 11E25

Pavel Hrubeš
Affiliation: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
Address at time of publication: Department of Computer Science, University of Calgary, Alberta T2N 1N4, Canada
Email: pahrubes@math.ias.edu

Avi Wigderson
Affiliation: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
MR Author ID: 182810
Email: avi@ias.edu

Amir Yehudayoff
Affiliation: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
Address at time of publication: Department of Mathematics, Technion–IIT, Haifa 32000, Israel
Email: amir.yehudayoff@gmail.com

Keywords: Algebraic complexity, composition of sums of squares
Received by editor(s): April 30, 2010
Received by editor(s) in revised form: December 28, 2010
Published electronically: February 2, 2011
Additional Notes: The authors were supported in part by NSF Grant CCF 0832797.