Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-021 | 21st February 2010 00:01

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


Authors: Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Publication: 21st February 2010 11:28
Downloads: 1845


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 \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that there exists an identity
\label{eqn:hwy def}
(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} ,
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 \emph{super-linear} lower bound on $n$ in \eqref{eqn:hwy def}, namely, $n\geq k^{1+\epsilon}$ with $\eps >0$, implies an \emph{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 \biq\m polynomial $h(X,Y)$, namely
\label{eqn:hwy def2}
h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} .
Again, proving $n\geq k^{1+\epsilon}$ in \eqref{eqn:hwy def2} for {\em any} explicit $h$ over the complex numbers
gives an \emph{exponential} lower bound for the non-commutative permanent.
Our proofs relies on several new structure theorems for non-commutative circuits,
as well as a non-commutative analog of Valiant's completeness of the permanent.

We proceed to prove such super-linear bounds in some restricted cases.
We prove that $n \geq \Omega(k^{6/5})$ in \eqref{eqn:hwy def},
if $f_{1 },\dots, f_{n}$ are required to have {\em integer} coefficients.
Over the {\em real} numbers, we construct an explicit \biq\m polynomial $h$ such that $n$ in (\ref{eqn:hwy def2}) must be at least $\Omega(k^{2})$. Unfortunately, these results do 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 \emph{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 non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.

ISSN 1433-8092 | Imprint