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

HrubeÅ¡, Pavel^1, 2 ; Wigderson, Avi¹ ; Yehudayoff, Amir^1, 3

¹ School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
² Department of Computer Science, University of Calgary, Alberta T2N 1N4, Canada
³ Department of Mathematics, Technion–IIT, Haifa 32000, Israel

Journal of the American Mathematical Society, Tome 24 (2011) no. 3, pp. 871-898

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-2011-00694-2

Bibliographie

[1] Barvinok, Alexander Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor Random Structures Algorithms 1999 29 61

[2] Baur, Walter, Strassen, Volker The complexity of partial derivatives Theoret. Comput. Sci. 1983 317 330

[3] Bã¼Rgisser, Peter Completeness and reduction in algebraic complexity theory 2000

[4] Chien, Steve, Sinclair, Alistair Algebras with polynomial identities and computing the determinant SIAM J. Comput. 2007 252 266

[5] Chien, Steve, Rasmussen, Lars, Sinclair, Alistair Clifford algebras and approximating the permanent 2002 222 231

[6] Von Zur Gathen, Joachim Algebraic complexity theory 1988 317 347

[7] Godsil, C. D., Gutman, I. On the matching polynomial of a graph 1981 241 249

[8] Hyafil, Laurent On the parallel evaluation of multivariate polynomials SIAM J. Comput. 1979 120 123

[9] Hurwitz, A. Über die Komposition der quadratischen Formen Math. Ann. 1922 1 25

[10] James, I. M. On the immersion problem for real projective spaces Bull. Amer. Math. Soc. 1963 231 238

[11] Jerrum, Mark, Sinclair, Alistair, Vigoda, Eric A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries J. ACM 2004 671 697

[12] Karmarkar, N., Karp, R., Lipton, R., Lovã¡Sz, L., Luby, M. A Monte Carlo algorithm for estimating the permanent SIAM J. Comput. 1993 284 293

[13] Lam, Kee Yuen Some new results on composition of quadratic forms Invent. Math. 1985 467 474

[14] Lam, T. Y., Smith, Tara L. On Yuzvinsky’s monomial pairings Quart. J. Math. Oxford Ser. (2) 1993 215 237

[15] Nisan, Noam, Wigderson, Avi Lower bounds on arithmetic circuits via partial derivatives Comput. Complexity 1996/97 217 234

[16] Pfister, Albrecht Zur Darstellung definiter Funktionen als Summe von Quadraten Invent. Math. 1967 229 237

[17] Raz, Ran Multi-linear formulas for permanent and determinant are of super-polynomial size 2004 633 641

[18] Raz, Ran Elusive functions and lower bounds for arithmetic circuits 2008 711 720

[19] Raz, Ran, Yehudayoff, Amir Lower bounds and separations for constant depth multilinear circuits 2008 128 139

[20] Raz, Ran, Shpilka, Amir, Yehudayoff, Amir A lower bound for the size of syntactically multilinear arithmetic circuits SIAM J. Comput. 2008 1624 1647

[21] Shapiro, Daniel B. Compositions of quadratic forms 2000

[22] Strassen, Volker Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten Numer. Math. 1972/73 238 251

[23] Strassen, Volker Vermeidung von Divisionen J. Reine Angew. Math. 1973 184 202

[24] Tiwari, Prasoon, Tompa, Martin A direct version of Shamir and Snir’s lower bounds on monotone circuit depth Inform. Process. Lett. 1994 243 248

[25] Valiant, L. G. Completeness classes in algebra 1979 249 261

[26] Winograd, Shmuel On the number of multiplications necessary to compute certain functions Comm. Pure Appl. Math. 1970 165 179

[27] Yiu, Paul Y. H. Sums of squares formulae with integer coefficients Canad. Math. Bull. 1987 318 324

[28] Yiu, Paul Y. H. On the product of two sums of 16 squares as a sum of squares of integral bilinear forms Quart. J. Math. Oxford Ser. (2) 1990 463 500

[29] Yuzvinsky, Sergey A series of monomial pairings Linear and Multilinear Algebra 1984 109 119