TY - GEN

T1 - Black-box identity testing of depth-4 multilinear circuits

AU - Saraf, Shubhangi

AU - Volkovich, Ilya

PY - 2011

Y1 - 2011

N2 - We study the problem of identity testing for multilinear ΣΠΣΠ(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(k3), 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 [3], 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 ΣΠΣΠ(k) circuits [13] ran in quasi-polynomial- time, with the running time being nO(k6 log(k) log2 s ). We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [17], on the identity testing for sparse polynomials, to yield the full result.

AB - We study the problem of identity testing for multilinear ΣΠΣΠ(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(k3), 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 [3], 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 ΣΠΣΠ(k) circuits [13] ran in quasi-polynomial- time, with the running time being nO(k6 log(k) log2 s ). We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [17], on the identity testing for sparse polynomials, to yield the full result.

KW - arithmetic circuits

KW - bounded depth circuits

KW - derandomization

KW - multilinear circuits

KW - polynomial identity testing

UR - http://www.scopus.com/inward/record.url?scp=79959731254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959731254&partnerID=8YFLogxK

U2 - 10.1145/1993636.1993693

DO - 10.1145/1993636.1993693

M3 - Conference contribution

AN - SCOPUS:79959731254

SN - 9781450306911

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 421

EP - 430

BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing

T2 - 43rd ACM Symposium on Theory of Computing, STOC'11

Y2 - 6 June 2011 through 8 June 2011

ER -