Remote Access Journal of the American Mathematical Society
Green Open Access

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

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

  • 1. V. Arvind and S. Srinivasan.
    On the hardness of the noncommutative determinant.
    STOC 10', pages 677-686, 2010.
  • 2. A. Barvinok.
    A simple polynomial time algorithm to approximate the permanent within a simply exponential factor.
    Random Structures and Algorithms 14(1), pages 29-61, 1999. MR 1662270 (2000a:68044)
  • 3. W. Baur and V. Strassen.
    The complexity of partial derivatives.
    Theoretical Computer Science (22), pages 317-330, 1983. MR 693063 (84c:68027)
  • 4. P. Burgisser.
    Completeness and reduction in algebraic complexity theory.
    Springer-Verlag, Berlin, Heidelberg, 2000. MR 1771845 (2001g:68030)
  • 5. S. Chien and A. Sinclair.
    Algebras with polynomial identities and computing the determinant.
    SIAM J. on Comput. 37, pages 252-266, 2007. MR 2306292 (2008e:68048)
  • 6. S. Chien, L. Rasmussen and A. Sinclair.
    Clifford algebras and approximating the permanent.
    STOC 02', pages 222-231, 2002. MR 2121146
  • 7. J. von zur Gathen.
    Algebraic complexity theory.
    Ann. Rev. Comp. Sci. (3), pages 317-347, 1988. MR 1001207 (91a:68150)
  • 8. C. Godsil and I. Gutman.
    On the matching polynomial of a graph.
    Algebraic Methods in Graph Theory, pages 241-249, 1981. MR 642044 (83b:05101)
  • 9. L. Hyafil.
    On the parallel evaluation of multivariate polynomials.
    SIAM J. Comput. 8, pages 120-123, 1979. MR 529584 (80c:68031)
  • 10. 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.
  • 11. P. Hrubeš and A. Yehudayoff.
    Homogeneous formulas and symmetric polynomials.
    Comput. Complex., to appear.
  • 12. P. Hrubeš, A. Wigderson and A. Yehudayoff.
    Relationless completeness and separations.
    CCC 10', pages 280-290, 2010.
  • 13. A. Hurwitz.
    Über die Komposition der quadratischen Formen von beliebigvielen Variabeln.
    Nach. Ges. der Wiss. Göttingen, pages 309-316, 1898.
  • 14. A. Hurwitz.
    Über die Komposition der quadratischen Formen.
    Math. Ann., 88, pages 1-25, 1923. MR 1512117
  • 15. I. M. James.
    On the immersion problem for real projective spaces.
    Bull. Amer. Math. Soc. 69, pages 231-238, 1967. MR 0144355 (26:1900)
  • 16. M. Jerrum, A. Sinclair and E. Vigoda.
    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
    J. ACM 51(4), pages 671-697, 2004. MR 2147852 (2006b:15013)
  • 17. S. Jukna.
    Boolean function complexity: advances and frontiers.
    Book in preparation.
  • 18. N. Karmarkar, R. Karp, R. Lipton, L. Lovasz and M. Luby.
    A Monte-Carlo algorithm for estimating the permanent.
    SIAM J. Comput. 22 (2), pages 284-293, 1993. MR 1207785 (94h:15004)
  • 19. T. Kirkman.
    On pluquatemions, and horaoid products of sums of $ n$ squares.
    Philos. Mag. (ser. 3), 33, pages 447-459; 494-509, 1848.
  • 20. K. Y. Lam.
    Some new results on composition of quadratic forms.
    Invent. Math. 79 (3), pages 467-474, 1985. MR 782229 (86e:11027)
  • 21. T. Y. Lam and T. Smith.
    On Yuzvinsky's monomial pairings.
    Quart. J. Math. Oxford. 44 (2), pages 215-237, 1993. MR 1222375 (94f:11025)
  • 22. K. Mulmuley.
    On P vs. NP, Geometric Complexity Theory, and the Riemann Hypothesis.
    Technical Report, Computer Science Department, The University of Chicago, 2009.
  • 23. N. Nisan.
    Lower bounds for non-commutative computation.
    STOC 91', pages 410-418, 1991.
  • 24. N. Nisan and A. Wigderson.
    Lower bounds on arithmetic circuits via partial derivatives.
    Computational Complexity (6), pages 217-234, 1996. MR 1486927 (99f:68107)
  • 25. A. Pfister.
    Zur Darstellung definiter Funktionen als Summe von Quadraten.
    Invent. Math. 4, pages 229-237, 1967. MR 0222043 (36:5095)
  • 26. J. Radon.
    Lineare Scharen orthogonalen Matrizen.
    Abh. Math. Sem. Univ. Hamburg 1, pages 2-14, 1922.
  • 27. R. Raz.
    Multi-linear formulas for permanent and determinant are of super-polynomial size.
    STOC 04', pages 633-641, 2004. MR 2121652 (2005j:68045)
  • 28. R. Raz.
    Elusive functions and lower bounds for arithmetic circuits.
    STOC 08', pages 711-720, 2010. MR 2582923
  • 29. R. Raz and A. Yehudayoff.
    Lower bounds and separation for constant depth multilinear circuits.
    CCC 08', pages 128-139, 2008. MR 2513495 (2010e:68076)
  • 30. R. Raz, A. Shpilka and A. Yehudayoff.
    A lower bound for the size of syntactically multilinear arithmetic circuits.
    SIAM J. Comput. 38 (4), pages 1624-1647, 2008. MR 2465561 (2010d:68053)
  • 31. D. B. Shapiro.
    Composition of quadratic forms.
    W. de Gruyter Verlag, 2000. MR 1786291 (2002f:11046)
  • 32. V. Strassen.
    Die berechnungskomplexitat von elementarsymmetrischen funktionen und von interpolationskoeffizienten.
    Numerische Mathematik (20), pages 238-251, 1973. MR 0324947 (48:3296)
  • 33. V. Strassen.
    Vermeidung von Divisionen.
    J. Reine Angew. Math. 264, pages 182-202, 1973. MR 0521168 (58:25128)
  • 34. P. Tiwari and M. Tompa.
    A direct version of Shamir and Snir's lower bound on monotone circuit depth.
    IPL, pages 243-248, 1994. MR 1266720 (95c:68112)
  • 35. L. G. Valiant.
    Completeness classes in algebra.
    STOC '79, pages 249-261, 1979. MR 564634 (83e:68046)
  • 36. S. Winograd.
    On the number of multiplications needed to compute certain functions.
    Comm. on Pure and Appl. Math. (23), pages 165-179, 1970. MR 0260150 (41:4778)
  • 37. P. Yiu.
    Sums of squares formulae with integer coefficients.
    Canad. Math. Bull. , 30, pages 318-324, 1987. MR 906354 (88m:11019)
  • 38. P. Yiu.
    On the product of two sums of 16 squares as a sum of squares of integral bilinear forms.
    Quart. J. Math. Oxford. 41 (2), pages 463-500, 1990. MR 1081107 (91m:11027)
  • 39. S. Yuzvinsky.
    A series of monomial pairings.
    Linear and Multilinear Algebra 15, pages 19-119, 1984. MR 740665 (85e:11028)

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

Avi Wigderson
Affiliation: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540

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

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.

American Mathematical Society