Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-046 | 2nd April 2011 19:43

Black-Box Identity Testing of Depth-4 Multilinear Circuits


Authors: Shubhangi Saraf, Ilya Volkovich
Publication: 3rd April 2011 03:29
Downloads: 2865


We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic
identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is $(ns)^{O(k^3)}$, where $n$ is the number of variables,
$s$ is the size of the circuit and $k$ is the fan-in of the top gate.

The importance of this model arises from \cite{AgrawalVinay08}, where it was shown that derandomizing black-box polynomial identity testing for general depth-$4$ circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits.
Prior to our work, the best PIT algorithm
for multilinear $\Spsp(k)$ circuits~\cite{KMSV10} ran in quasi-polynomial-time, with the running time being $n^{O(k^6 \log(k) \log^2 s )}$.

We obtain our results by showing a strong {\em structural result} for multilinear $\Spsp(k)$ circuits that compute the zero polynomial.
We show that under some mild technical conditions, any gate of such a circuit must compute a {\em sparse} polynomial.
We then show how to combine the structure theorem with a result by Klivans and Spielman~\cite{KlivansSpielman01}, on the identity testing for sparse polynomials, to yield the full result.

ISSN 1433-8092 | Imprint