ECCC-Report TR10-013https://eccc.weizmann.ac.il/report/2010/013Comments and Revisions published for TR10-013en-usTue, 09 Feb 2010 00:40:20 +0200
Revision 1
| From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits |
Nitin Saxena,
C. Seshadhri
https://eccc.weizmann.ac.il/report/2010/013#revision1We 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.Tue, 09 Feb 2010 00:40:20 +0200https://eccc.weizmann.ac.il/report/2010/013#revision1
Paper TR10-013
| From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits |
Nitin Saxena,
C. Seshadhri
https://eccc.weizmann.ac.il/report/2010/013We 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.Sun, 31 Jan 2010 22:13:01 +0200https://eccc.weizmann.ac.il/report/2010/013