Diagonal Circuit Identity Testing and Lower Bounds

摘要

In this paper we give the first deterministic polynomial time algorithm for testing whether a diagonal depth-3 circuit C(x{sub}1,...,x{sub}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 F) of the form: C(x{sub}1,...,x{sub}n):=∑(L{sub}(i,1)){sup}(e{sub}i,1)...(L{sub}(i,s)){sup}(e{sub}i,s) (i from 1 to k) where, each L{sub}(i,j) is a sum of univariate polynomials in F[x{sub}1,...,x{sub}n]. We can test whether C is zero deterministically in poly(size(C), max{sub}i{(1+e{sub}(i,1)) ... (1+e{sub}(i,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(x{sub}1,...,x{sub}n) computes the determinant (or permanent) of an m×m formal matrix with a "small" s=o (m/log m) then k=2{sup}(Ω(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 homogeneous diagonal circuits (deterministically in poly(nk log(d)) field operations over finite fields).