Diagonal Circuit Identity Testing and Lower

Abstract. In this paper we give the first deterministic polynomial time algorithm for testing whether a diagonal depth-3 circuit C(x1,..., xn) (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 F) of the form: C(x1,..., xn):= k∑ i=1 L ei,1 i,1 · · ·Lei,si,s where, each Li,j is a sum of univariate polynomials in F[x1,..., xn]. We can test whether C is zero deterministically in poly(size(C), maxi{(1 + ei,1) · · · (1 + ei,s)}) field operations. In particular, this gives a deterministic polynomial time identity test for general depth-3 circuits C when the d:=degree(C) is logarithmic in the size(C). 2. We prove that if the above circuit C(x1,..., xn) computes the de-terminant (or permanent) of an m×m formal matrix with a “small” s = o m log m then k = 2Ω(m). Our lower bounds work for all fields F. (Previous exponential lower bounds for depth-3 only work for nonzero characteristic.) 3. We also present an exponentially faster identity test for homoge-neous diagonal circuits (deterministically in poly(nk log(d)) field op-erations over finite fields)