About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
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.