Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
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
Published electronically: February 2, 2011
MathSciNet review: 2784331
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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

$\displaystyle (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 $

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

$\displaystyle (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$

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.


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


Similar Articles

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


Additional Information

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
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

DOI: http://dx.doi.org/10.1090/S0894-0347-2011-00694-2
PII: S 0894-0347(2011)00694-2
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.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.