From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuitsFrom sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits

Access Restriction
Subscribed

 Author Saxena, Nitin ♦ Seshadhri, C. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Chinese remaindering ♦ Sylvester-Gallai ♦ Combinatorial design ♦ Depth-3 circuit ♦ Ideal theory ♦ Identities ♦ Incidence geometry Abstract We study the problem of identity testing for depth-3 circuits of top fanin $\textit{k}$ and degree $\textit{d}.$ We give a new structure theorem for such identities that improves the known deterministic $d^{k}^{O(k)}-time$ blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes $d^{O(k^{2})}-time.$ Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture 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-3 identity 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. The most important aspect of this work is relating a field-dependent quantity, the Sylvester-Gallai rank bound, to the rank of 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 bounds). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 5 Page Count 33 Starting Page 1 Ending Page 33
Source: ACM Digital Library