TR09-116 Authors: Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

Publication: 16th November 2009 22:16

Downloads: 2778

Keywords:

We give the first sub-exponential time deterministic polynomial

identity testing algorithm for depth-$4$ multilinear circuits with

a small top fan-in. More accurately, our algorithm works for

depth-$4$ circuits with a plus gate at the top (also known as

$\Spsp$ circuits) and has a running time of

$\exp(\poly(\log(n),\log(s),k))$ where $n$ is the number of

variables, $s$ is the size of the circuit and $k$ is the fan-in of

the top gate. In particular, when the circuit is of polynomial (or

quasi-polynomial) size, our algorithm runs in quasi-polynomial

time. In \cite{AgrawalVinay08}, it was shown that derandomizing

polynomial identity testing for general $\Spsp$ circuits implies a

derandomization of polynomial identity testing in general

arithmetic circuits. Prior to this work sub-exponential time

deterministic algorithms were known for depth-$3$ circuits with

small top fan-in and for very restricted versions of depth-$4$

circuits.

\sloppy The main ingredient in our proof is a new structural

theorem for multilinear $\Spsp(k)$ circuits. Roughly, this theorem

shows that any nonzero multilinear $\Spsp(k)$ circuit contains an

`embedded' nonzero multilinear $\Sps(k)$ circuit. Using ideas from

previous works on identity testing of sums of read-once formulas

and of depth-$3$ multilinear circuits, we are able to exploit this

structure and obtain an identity testing algorithm for multilinear

$\Spsp(k)$ circuits.