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.
A direct application of our theorem improves the known
deterministic d^{k^k}-time black-box identity test over rationals (Kayal-Saraf, FOCS 2009)
to one that takes d^{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 settles
affirmatively the stronger rank conjectures posed by Dvir-Shpilka (STOC 2005)
and Kayal-Saraf (FOCS 2009).
Our techniques provide a unified framework that actually beats all
known rank bounds and hence gives the best running time (for *every* field)
for black-box identity tests.

Our main theorem (almost optimally) pins down the relation between higher dimensional Sylvester-Gallai
theorems and the rank of depth-3 identities in a very transparent
manner. The existence of this was hinted at by Dvir-Shpilka (STOC 2005), but
first proven, for reals, by Kayal-Saraf (FOCS 2009).
We introduce the concept of Sylvester-Gallai rank bounds for any field,
and show the intimate connection between this and depth-3 identity rank bounds.
We also prove the first ever theorem about high dimensional Sylvester-Gallai
configurations over *any* field. Our proofs and techniques are very
different from previous results and devise a very interesting ensemble of combinatorics and algebra.
The latter concepts are ideal theoretic and involve a new Chinese remainder theorem.
Our proof methods explain the structure of *any* depth-3
identity C: there is a nucleus of C that forms a low rank identity, while the remainder
is a high dimensional Sylvester-Gallai configuration.

Results have been strengthened to ALL fields.

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 real identities,
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.