\input zb-basic
\input zb-ioport
\iteman{io-port 05317218}
\itemau{Saxena, Nitin}
\itemti{Diagonal circuit identity testing and lower bounds.}
\itemso{Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7--11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 60-71 (2008).}
\itemab
Summary: In this paper we give the first deterministic polynomial time algorithm for testing whether a diagonal depth-3 circuit $C(x _{1},\dots ,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: 1. Suppose we are given a depth-4 circuit (over any field $\mathbb{F}$) of the form: $$C({x_1},\ldots,{x_n}):=\sum_{i=1}^k L_{i,1}^{e_{i,1}}\cdots L_{i,s}^{e_{i,s}}$$ where each $L _{i,j }$ is a sum of univariate polynomials in $\mathbb{F}[{x_1},\ldots,{x_n}]$. We can test whether $C$ is zero deterministically in $\text{poly}(\text{size}(C), \max _{i }\{(1 + e _{i,1}) \dots (1 + e _{i,s })\})$ field operations. In particular, this gives a deterministic polynomial time identity test for general depth-3 circuits $C$ when the $d: =\text {degree}(C)$ is logarithmic in the $\text {size}(C)$. 2. We prove that if the above circuit $C(x _{1},\dots ,x _{n })$ computes the determinant (or permanent) of an $m\times m$ formal matrix with a ``small'' $s=o(\frac{m}{\log m})$ then $k = 2^{\Omega (m)}$. Our lower bounds work for all fields $\mathbb{F}$. (Previous exponential lower bounds for depth-3 only work for nonzero characteristic.) 3. We also present an exponentially faster identity test for homogeneous diagonal circuits (deterministically in $\text {poly}(nk\log (d))$ field operations over finite fields).
\itemrv{~}
\itemcc{}
\itemut{arithmetic circuit; identity testing; depth 3; depth 4; determinant; permanent; lower bounds}
\itemli{doi:10.1007/978-3-540-70575-8\_6}
\end