Thumbnail
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