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