Abstract:

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-3 circuit C(\arg{x}{n}) (i.e. C is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only if there are exponentially many linear functions. Our techniques generalize to the following new results:
\begin{enumerate}
\item Suppose we are given a depth-3 circuit (over any field \FF) of the form:

where, the \ell_{i,j}'s are linear functions living in \FF[\arg{x}{n}]. We can test whether C is zero deterministically in poly\left(nk,max\{(1+e_{i,1})\cdots(1+e_{i,s})\mid 1\le i\le k\}\right) field operations. This immediately gives a deterministic poly(nk2^d) time identity test for general depth-3 circuits of degree d.
\item We prove that if the above circuit C(\arg{x}{n}) computes the determinant (or permanent) of an m\times m formal matrix with a ``small'' s=o\left(\frac{m}{\log m}\right) then k=2^{\Omega(m)}.
Our lower bounds work for all fields \FF. (Previous exponential lower bounds for depth-3 only work for nonzero characteristic.)
\item We present applications of our ideas to depth-4 circuits and an exponentially faster identity test for homogeneous diagonal circuits (deterministically in poly(n k\log(d)) field operations over
finite fields).
\end{enumerate}