Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Black-Box Identity Testing of Depth-4 Multilinear Circuits
event speaker icon
Ilya Volkovich (Ph.D. Thesis Seminar)
event date icon
Wednesday, 04.05.2011, 12:30
event location icon
Taub 337
event speaker icon
Advisor: Assoc. Prof. Amir Shpilka.
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.