Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Non-commutative circuits and the sum-of-squares problem
HTML articles powered by AMS MathViewer

by Pavel Hrubeš, Avi Wigderson and Amir Yehudayoff PDF
J. Amer. Math. Soc. 24 (2011), 871-898 Request permission

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

References
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
  • 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
  • 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.
  • © Copyright 2011 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • 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
  • MathSciNet review: 2784331