Theory Seminar: Black-Box Identity Testing of Depth-4 Multilinear Circuits

Ilya Volkovich (CS Technion)

Wednesday, 04.05.2011, 12:30

Room 337-8 Taub Bld.

A central problem in algebraic complexity theory and algorithms design is the problem of
Polynomial Identity Testing (PIT): given an arithmetic circuit $C$ over a field $\F$, with input variables $x_1, x_2, ... , x_n$, determine whether $C$ computes the identically zero polynomial. Numerous applications and connections to other algorithmic and number theoretic problems further emphasize the significance of PIT. Among the examples are algorithms for finding perfect matchings in graphs \cite{Lovasz79,MVV87}, primality testing \cite{AKS04}, and many more.
We study the problem of PIT for multilinear $\Sigma \Pi \Sigma \Pi (k) $ circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic PIT algorithm for such circuits. Our results also hold in the black-box setting. 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. We obtain our results by showing a strong structural result
for multilinear $\Sigma \Pi \Sigma \Pi (k) $ circuits that compute the zero polynomial.