Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-124 | 23rd November 2007 00:00

Diagonal Circuit Identity Testing and Lower Bounds


Authors: Nitin Saxena
Publication: 7th December 2007 11:57
Downloads: 3647


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:
\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).

ISSN 1433-8092 | Imprint