ECCC-Report TR11-046https://eccc.weizmann.ac.il/report/2011/046Comments and Revisions published for TR11-046en-usSun, 03 Apr 2011 03:29:24 +0300
Paper TR11-046
| Black-Box Identity Testing of Depth-4 Multilinear Circuits |
Shubhangi Saraf,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2011/046We 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.Sun, 03 Apr 2011 03:29:24 +0300https://eccc.weizmann.ac.il/report/2011/046