Back to Search
Start Over
From Sylvester-Gallai Configurations to Rank Bounds: Improved Blackbox Identity Test for Depth-3 Circuits.
- Source :
- Journal of the ACM; Oct2013, Vol. 60 Issue 5, p1-33, 33p
- Publication Year :
- 2013
-
Abstract
- We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities that improves the known deterministic -time blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes -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). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00045411
- Volume :
- 60
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Journal of the ACM
- Publication Type :
- Academic Journal
- Accession number :
- 91749662
- Full Text :
- https://doi.org/10.1145/2528403