### Diagonal circuit identity testing and lower bounds (2007).Diagonal circuit identity testing and lower bounds (2007).

Access Restriction
Open

 Author Saxena, Nitin Source CiteSeerX Content type Text File Format PDF
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Diagonal Circuit Identity Testing ♦ Field Operation ♦ Linear Function ♦ Depth-3 Circuit ♦ Depth-4 Circuit ♦ Depth-3 Work ♦ Homogeneous Diagonal Circuit ♦ First Deterministic Polynomial Time Algorithm ♦ Many Linear Function ♦ Previous Exponential ♦ Faster Identity Test ♦ New Result ♦ Diagonal Depth-3 Circuit ♦ Formal Matrix ♦ Finite Field ♦ Deterministic Poly ♦ Time Identity Test ♦ General Depth-3 Circuit ♦ Present Application 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-3 circuit (over any field F) of the form: C(x1,..., xn):= k∑ i=1 ei,1 i,1 · · ·  ei,s i,s where, the i,j ’s are linear functions living in F[x1,..., xn]. We can test whether C is zero deterministically in poly (nk,max{(1 + ei,1) · · · (1 + ei,s) 1 6 i 6 k}) field operations. This immediately gives a deterministic poly(nk2d) time identity test for general depth-3 circuits of degree d. 2. We prove that if the above circuit C(x1,..., xn) computes the determinant (or permanent) of an m × m formal matrix with a “small ” s = o m logm 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 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). Educational Role Student ♦ Teacher Age Range above 22 year Educational Use Research Education Level UG and PG ♦ Career/Technical Study Learning Resource Type Article Publisher Date 2007-01-01