TR10-021 Authors: Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Publication: 21st February 2010 11:28

Downloads: 3787

Keywords:

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

\begin{equation}

\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} ,

\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 \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

\begin{equation}

\label{eqn:hwy def2}

h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} .

\end{equation}

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.