期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 fi=fi(XY) is a bilinear form in X=x1xk and Y=y1yk . Over the complex numbers, we show that a sufficiently strong \emph{super-linear} lower bound on n in \eqref{eqn:hwy def}, namely, nk1+ with \eps0, 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(XY) , namely
\begin{equation}
\label{eqn:hwy def2}
h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} .
\end{equation}
Again, proving nk1+ 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(k65) in \eqref{eqn:hwy def},
if f1fn 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 (k2). 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.
