ECCC-Report TR09-116https://eccc.weizmann.ac.il/report/2009/116Comments and Revisions published for TR09-116en-usMon, 16 Nov 2009 22:16:09 +0200
Paper TR09-116
| Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in |
Zohar Karnin,
Partha Mukhopadhyay,
Amir Shpilka,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2009/116We 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.Mon, 16 Nov 2009 22:16:09 +0200https://eccc.weizmann.ac.il/report/2009/116