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

HTML articles powered by AMS MathViewer

- by Pavel Hrubeš, Avi Wigderson and Amir Yehudayoff
- J. Amer. Math. Soc.
**24**(2011), 871-898 - DOI: https://doi.org/10.1090/S0894-0347-2011-00694-2
- Published electronically: February 2, 2011
- PDF | 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

- V. Arvind and S. Srinivasan. On the hardness of the noncommutative determinant. STOC 10’, pages 677-686, 2010.
- Alexander Barvinok,
*Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor*, Random Structures Algorithms**14**(1999), no. 1, 29–61. MR**1662270**, DOI 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X - Walter Baur and Volker Strassen,
*The complexity of partial derivatives*, Theoret. Comput. Sci.**22**(1983), no. 3, 317–330. MR**693063**, DOI 10.1016/0304-3975(83)90110-X - Peter Bürgisser,
*Completeness and reduction in algebraic complexity theory*, Algorithms and Computation in Mathematics, vol. 7, Springer-Verlag, Berlin, 2000. MR**1771845**, DOI 10.1007/978-3-662-04179-6 - Steve Chien and Alistair Sinclair,
*Algebras with polynomial identities and computing the determinant*, SIAM J. Comput.**37**(2007), no. 1, 252–266. MR**2306292**, DOI 10.1137/S0097539705447359 - Steve Chien, Lars Rasmussen, and Alistair Sinclair,
*Clifford algebras and approximating the permanent*, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 222–231. MR**2121146**, DOI 10.1145/509907.509944 - Joachim von zur Gathen,
*Algebraic complexity theory*, Annual review of computer science, Vol. 3, Annual Reviews, Palo Alto, CA, 1988, pp. 317–347. MR**1001207** - C. D. Godsil and I. Gutman,
*On the matching polynomial of a graph*, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 241–249. MR**642044** - Laurent Hyafil,
*On the parallel evaluation of multivariate polynomials*, SIAM J. Comput.**8**(1979), no. 2, 120–123. MR**529584**, DOI 10.1137/0208010 - P. Hrubeš, A. Wigderson and A. Yehudayoff. An asymptotic bound on composition number of integer sums of squares formulas. To appear in Canadian Mathematical Bulletin.
- P. Hrubeš and A. Yehudayoff. Homogeneous formulas and symmetric polynomials. Comput. Complex., to appear.
- P. Hrubeš, A. Wigderson and A. Yehudayoff. Relationless completeness and separations. CCC 10’, pages 280–290, 2010.
- A. Hurwitz. Über die Komposition der quadratischen Formen von beliebigvielen Variabeln. Nach. Ges. der Wiss. Göttingen, pages 309–316, 1898.
- A. Hurwitz,
*Über die Komposition der quadratischen Formen*, Math. Ann.**88**(1922), no. 1-2, 1–25 (German). MR**1512117**, DOI 10.1007/BF01448439 - I. M. James,
*On the immersion problem for real projective spaces*, Bull. Amer. Math. Soc.**69**(1963), 231–238. MR**144355**, DOI 10.1090/S0002-9904-1963-10930-1 - Mark Jerrum, Alistair Sinclair, and Eric Vigoda,
*A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries*, J. ACM**51**(2004), no. 4, 671–697. MR**2147852**, DOI 10.1145/1008731.1008738 - S. Jukna. Boolean function complexity: advances and frontiers. Book in preparation.
- N. Karmarkar, R. Karp, R. Lipton, L. Lovász, and M. Luby,
*A Monte Carlo algorithm for estimating the permanent*, SIAM J. Comput.**22**(1993), no. 2, 284–293. MR**1207785**, DOI 10.1137/0222021 - T. Kirkman. On pluquatemions, and horaoid products of sums of $n$ squares. Philos. Mag. (ser. 3), 33, pages 447–459; 494-509, 1848.
- Kee Yuen Lam,
*Some new results on composition of quadratic forms*, Invent. Math.**79**(1985), no. 3, 467–474. MR**782229**, DOI 10.1007/BF01388517 - T. Y. Lam and Tara L. Smith,
*On Yuzvinsky’s monomial pairings*, Quart. J. Math. Oxford Ser. (2)**44**(1993), no. 174, 215–237. MR**1222375**, DOI 10.1093/qmath/44.2.215 - K. Mulmuley. On P vs. NP, Geometric Complexity Theory, and the Riemann Hypothesis. Technical Report, Computer Science Department, The University of Chicago, 2009.
- N. Nisan. Lower bounds for non-commutative computation. STOC 91’, pages 410–418, 1991.
- Noam Nisan and Avi Wigderson,
*Lower bounds on arithmetic circuits via partial derivatives*, Comput. Complexity**6**(1996/97), no. 3, 217–234. MR**1486927**, DOI 10.1007/BF01294256 - Albrecht Pfister,
*Zur Darstellung definiter Funktionen als Summe von Quadraten*, Invent. Math.**4**(1967), 229–237 (German). MR**222043**, DOI 10.1007/BF01425382 - J. Radon. Lineare Scharen orthogonalen Matrizen. Abh. Math. Sem. Univ. Hamburg 1, pages 2–14, 1922.
- Ran Raz,
*Multi-linear formulas for permanent and determinant are of super-polynomial size*, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 633–641. MR**2121652**, DOI 10.1145/1007352.1007353 - Ran Raz,
*Elusive functions and lower bounds for arithmetic circuits*, STOC’08, ACM, New York, 2008, pp. 711–720. MR**2582923**, DOI 10.1145/1374376.1374479 - Ran Raz and Amir Yehudayoff,
*Lower bounds and separations for constant depth multilinear circuits*, Twenty-Third Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2008, pp. 128–139. MR**2513495**, DOI 10.1109/CCC.2008.8 - Ran Raz, Amir Shpilka, and Amir Yehudayoff,
*A lower bound for the size of syntactically multilinear arithmetic circuits*, SIAM J. Comput.**38**(2008), no. 4, 1624–1647. MR**2465561**, DOI 10.1137/070707932 - Daniel B. Shapiro,
*Compositions of quadratic forms*, De Gruyter Expositions in Mathematics, vol. 33, Walter de Gruyter & Co., Berlin, 2000. MR**1786291**, DOI 10.1515/9783110824834 - Volker Strassen,
*Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten*, Numer. Math.**20**(1972/73), 238–251 (German, with English summary). MR**324947**, DOI 10.1007/BF01436566 - Volker Strassen,
*Vermeidung von Divisionen*, J. Reine Angew. Math.**264**(1973), 184–202 (German, with English summary). MR**521168** - Prasoon Tiwari and Martin Tompa,
*A direct version of Shamir and Snir’s lower bounds on monotone circuit depth*, Inform. Process. Lett.**49**(1994), no. 5, 243–248. MR**1266720**, DOI 10.1016/0020-0190(94)90061-2 - L. G. Valiant,
*Completeness classes in algebra*, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979) ACM, New York, 1979, pp. 249–261. MR**564634** - Shmuel Winograd,
*On the number of multiplications necessary to compute certain functions*, Comm. Pure Appl. Math.**23**(1970), 165–179. MR**260150**, DOI 10.1002/cpa.3160230204 - Paul Y. H. Yiu,
*Sums of squares formulae with integer coefficients*, Canad. Math. Bull.**30**(1987), no. 3, 318–324. MR**906354**, DOI 10.4153/CMB-1987-045-6 - Paul Y. H. Yiu,
*On the product of two sums of $16$ squares as a sum of squares of integral bilinear forms*, Quart. J. Math. Oxford Ser. (2)**41**(1990), no. 164, 463–500. MR**1081107**, DOI 10.1093/qmath/41.4.463 - Sergey Yuzvinsky,
*A series of monomial pairings*, Linear and Multilinear Algebra**15**(1984), no. 2, 109–119. MR**740665**, DOI 10.1080/03081088408817582

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