BLACKBOX IDENTITY TESTING FOR BOUNDED TOP-FANIN DEPTH-3 CIRCUITS: THE FIELD DOESN'T MATTER

Let C be a depth-3 circuit with n variables, degree d, and top-fanin k (called Sigma Pi Sigma(k, d, n) circuits) over base field F. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests whether C is identically zero. Klivans and Spielman [Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC), 2001, pp. 216-223] observed that the problem is open even when k is a constant. This case has been subjected to serious scrutiny over the past few years, starting from the work of Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404-1434]. We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time poly(n)d(k), regardless of the base field. The only field for which polynomial time algorithms were previously known is F - Q [N. Kayal and S. Saraf, Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198-207; N. Saxena and C. Seshadhri, Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010, pp. 21-29]. This is the first blackbox algorithm for depth-3 circuits that does not use the rank-based approaches of Karnin and Shpilka [Proceedings of the 24th Annual Conference on Computational Complexity (CCC), 2009, pp. 274-285]. We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a Sigma Pi Sigma(k, d, n) circuit to k variables but preserves the identity structure.