__
TR07-124 | 23rd November 2007 00:00
__

#### Diagonal Circuit Identity Testing and Lower Bounds

**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:

$$C(\arg{x}{n}):=\sum_{i=1}^k \ell_{i,1}^{e_{i,1}}\cdots\ell_{i,s}^{e_{i,s}}$$

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}