An almost optimal rank bound for depth-3 identities

Abstract

We study the problem of polynomial identity testing for depth-3 circuits of degree d and top fanin k. The rank of any such identity is essentially the minimum number of independent variables present. Small bounds on this quantity imply fast deterministic identity testers for these circuits. Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404-1434] initiated the study of the rank and showed that any depth-3 identity (barring some uninteresting corner cases) has a rank of 2O(k2)(log d)k-2. We show that the rank of a depth-3 identity is at most O(k3 log d). This bound is almost tight, since we also provide an identity of rank ω(k log d). Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka [Z. Karnin and A. Shpilka, in Proceedings of the 23rd CCC, 2008, pp. 280-291]. Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits: the rank of linear factors of a simple, minimal, and nonzero depth-3 circuit (over any field) is at most O(k3 log d). The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these ideas may lead to the goal of a deterministic polynomial time identity test for these circuits. © 2011 Society for Industrial and Applied Mathematics.