Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR09-116 | 15th November 2009 10:18

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

TR09-116
Authors: Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
Publication: 16th November 2009 22:16
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint