Access Restriction

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