We study the problem of identity testing for depth-3 circuits, over the field
of reals, of top fanin k and degree d (called sps(k,d) identities). We give a
new structure theorem for such identities and improve the known deterministic
d^{k^k}-time black-box identity test (Kayal & Saraf, FOCS 2009) to one that
takes d^{k^2}-time.

We achieve this exponential improvement by settling affirmatively the
"stronger" rank conjectures posed by Dvir & Shpilka (STOC 2005) and Kayal &
Saraf (FOCS 2009). For identities over R, the latter paper had shown a rank
bound of k^k (note the independence from d) for simple, minimal sps(k,d)
identities, which we improve to k^2.

Our main theorem (almost optimally) pins down the connection between higher
dimensional Sylvester-Gallai theorems and the rank of depth-3 identities in a
very transparent manner. Our proofs and techniques use a very interesting mix
of algebra and combinatorics. The algebraic part of the proof (which works over
any field) identifies a k^2-rank sub-identity, called the nucleus identity,
which somehow contains most of the "complexity" of an identity. This involves
new ideal properties including a generalized Chinese remainder theorem. Next,
we combine algebraic lemmas with some combinatorics to argue about the
remainder of the circuit (the non-nucleus part), bounding the rank of this
portion through higher dimensional versions of the Sylvester-Gallai Theorem.
Our proof methods explain the structure of any depth-3 identity C : the nucleus
of C is a low rank identity, while the remainder is a high dimensional
Sylvester-Gallai configuration.