From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits

Abstract

We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a newstructure theorem for such identities that improves the known deterministic dkO(k) -time blackbox identitytest over rationals [Kayal and Saraf, 2009] to one that takes dO(k2)-time. Our structure theorem essentiallysays that the number of independentvariables in a real depth-3 identity is very small. This theoremaffirmatively settles the strong rankconjecture posed by Dvir and Shpilka [2006].We devise various algebraic tools to study depth-3 identities, and use these tools to show that any depth-3identity contains a much smaller nucleus identity that contains most of the "complexity" of the main identity.The special properties of this nucleus allow us to get near optimal rank bounds for depth-3 identities. Themost important aspect of this work is relating a field-dependent quantity, the Sylvester-Gallai rank bound,to the rankof depth-3 identities. We also prove a high-dimensional Sylvester-Gallai theorem for all fields,and get a general depth-3 identity rank bound (slightly improving previous © 2013 ACM.