Revision #1 Authors: Nitin Saxena, C. Seshadhri

Accepted on: 9th February 2010 00:40

Downloads: 3944

Keywords:

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.

TR10-013 Authors: Nitin Saxena, C. Seshadhri

Publication: 31st January 2010 22:13

Downloads: 3728

Keywords:

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.