Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-116 | 15th November 2009 10:18

Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in



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$

\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.

ISSN 1433-8092 | Imprint