Blackbox Polynomial Identity Testing for Depth 3 Circuits
Authors:
- Neeraj KayalNKNeeraj Kayal
- Shubhangi SarafSSShubhangi Saraf
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 16 (02725428) , 198-207
Abstract
We study ¿¿¿(k) circuits, i.e., depth three arithmetic circuits with top fanin k. We give the first deterministic polynomial time blackbox identity test for ¿¿¿(k) circuits over the field Q of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is a structural theorem for ¿¿¿(k) circuits that compute the zero polynomial. In particular we show that if a ¿¿¿(k) circuit C = ¿i¿[k] Ai = ¿i¿[k] ¿j¿[d] ¿ij computing the zero polynomial, where each Ai is a product of linear forms with coefficients in ¿, is simple (gcd{Ai | i ¿ [k]} = 1) and minimal (for all proper nonempty subsets S ¿ [k], ¿i¿S Ai ¿ 0), then the rank (dimension of the span of the linear forms {¿ij | i ¿ [k],j ¿ [d]}) of C can be upper bounded by a function only of k. This proves a weak form of a conjecture of Dvir and Shpilka (STOC 2005) on the structure of identically zero depth three arithmetic circuits. Our blackbox identity test follows from this structural theorem by combining it with a construction of Karnin and Shpilka (CCC 2008). Our proof of the structure theorem exploits the geometry of finite point sets in ¿n. We identify the linear forms appearing in the circuit C with points in ¿n. We then show how to apply high dimensional versions of the Sylvester-Gallai Theorem, a theorem from incidence-geometry, to identify a special linear form appearing in C, such that on the subspace where the linear form vanishes, C restricts to a simpler circuit computing the zero polynomial. This allows us to build an inductive argument bounding the rank of our circuit. While the utility of such theorems from incidence geometry for identity testing has been hinted at before, our proof is the first to develop the connection fully and utilize it effectively.Keywords
This publication has 24 references indexed in Scilit:
- Sylvester–Gallai Theorems for Complex Numbers and QuaternionsDiscrete & Computational Geometry, 2006
- PRIMES is in PAnnals of Mathematics, 2004
- Primality and identity testing via Chinese remainderingJournal of the ACM, 2003
- Reducing Randomness via Irrational NumbersSIAM Journal on Computing, 2000
- A survey of Sylvester's problem and its generalizationsAequationes mathematicae, 1990
- Interpolating polynomials from their valuesJournal of Symbolic Computation, 1990
- Matching is as easy as matrix inversionCombinatorica, 1987
- A resolution of the sylvester-gallai problem of J.-P. serreDiscrete & Computational Geometry, 1986
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- Bisecants of Finite Collections of Sets in Linear SpacesCanadian Journal of Mathematics, 1966