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

1

,...,

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

poly

(

size

(

C

),

max

i

{(1 + 

e

i

,1

) ⋯ (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

: =degree(C) is logarithmic in the size(C).

1

We prove that if the above circuit

C

(

x

1

,...,

x

n

) computes the determinant (or permanent) of an

m

×

m

formal matrix with a “small”

$s=o\left(\frac{m}{\log m}\right)$

then

k

 = 2

Ω

(

m

)

. Our lower bounds work for all fields

$\mathbb{F}$

. (Previous exponential lower bounds for depth-3 only work for nonzero characteristic.)

1

We also present an exponentially faster identity test for homogeneous diagonal circuits (deterministically in

poly

(

nk

log(

d

)) field operations over finite fields).