Nitin Saxena
Skip Abstract Section
Abstract
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 that improves the known deterministic dkO(k)-time blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes dO(k2)-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir and Shpilka [2006].
We devise various algebraic tools to study depth-3 identities, and use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the “complexity” of the main identity. The special properties of this nucleus allow us to get near optimal rank bounds for depth-3 identities. The most important aspect of this work is relating a field-dependent quantity, the Sylvester-Gallai rank bound, to the rank of depth-3 identities. We also prove a high-dimensional Sylvester-Gallai theorem for all fields, and get a general depth-3 identity rank bound (slightly improving previous bounds).
- Agrawal, M. 2005. Proving lower bounds via pseudo-random generators. In Proceedings of the 25th Annual Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 92--105. Google Scholar
Digital Library
- Agrawal, M. 2006. Determinant versus permanent. In Proceedings of the 25th International Congress of Mathematicians (ICM). Vol. 3, 985--997.Google Scholar
- Agrawal, M. and Biswas, S. 2003. Primality and identity testing via Chinese remaindering. J. ACM 50, 4, 429--443. Google ScholarDigital Library
- Agrawal, M., Saha, C., Saptharishi, R., and Saxena, N. 2011. Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. Tech. rep. TR11-143, ECCC, http://eccc.hpi-web.de/report/2011/143/.Google Scholar
- Agrawal, M. and Saptharishi, R. 2009. Classifying polynomials and identity testing. Tech. rep., IIT Kanpur, http://www.cse.iitk.ac.in/manindra/survey/Identity.pdf.Google Scholar
- Agrawal, M. and Vinay, V. 2008. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS). 67--75. Google ScholarDigital Library
- Anderson, M., van Melkebeek, D., and Volkovich, I. 2011. Derandomizing polynomial identity testing for multilinear constant-read formulae. In Proceedings of the 26th Conference on Computational Complexity (CCC). 273--282. Google ScholarDigital Library
- Arvind, V. and Mukhopadhyay, P. 2010. The ideal membership problem and polynomial identity testing. Inf. Comput. 208, 4, 351--363. Google ScholarDigital Library
- Beecken, M., Mittmann, J., and Saxena, N. 2011. Algebraic independence and blackbox identity testing. In Proceedings of the 38th Annual International Colloquium on Automata, Languages and Programming (ICALP). 137--148. Google ScholarDigital Library
- Bhattacharyya, A., Dvir, Z., Saraf, S., and Shpilka, A. 2011. Tight lower bounds for 2-query LCCs over finite fields. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS). 638--647. Google ScholarDigital Library
- Bonnice, W. and Edelstein, M. 1967. Flats associated with finite sets in Pd. Niew. Arch. Wisk. 15, 11--14.Google Scholar
- Borwein, P. and Moser, W. O. J. 1990. A survey of Sylvesters problem and its generalizations. Aequationes Math. 40, 1, 111--135.Google ScholarCross Ref
- Chen, Z. and Kao, M. 2000. Reducing randomness via irrational numbers. SIAM J. Comput. 29, 4, 1247--1256. (Conference version in STOC 1997). Google ScholarDigital Library
- DeMillo, R. A. and Lipton, R. J. 1978. A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7, 4, 193--195.Google ScholarCross Ref
- Dvir, Z. and Shpilka, A. 2006. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput. 36, 5, 1404--1434. Google ScholarDigital Library
- Elkies, N. D., Pretorius, L. M., and Swanepoel, C. J. 2006. Sylvester-Gallai theorems for complex numbers and quaternions. Discrete Comput. Geometry 35, 3, 361--373.Google ScholarDigital Library
- Goldreich, O., Karloff, H., Schulman, L., and Trevisan, L. 2002. Lower bounds for linear locally decodable codes and private information retrieval. In Proceedings of the 17th Annual Computational Complexity Conference (CCC). 175--183. Google ScholarDigital Library
- Hansen, S. 1965. A generalization of a theorem of Sylvester on the lines determined by a finite point set. Math. Scand. 16, 175--180.Google ScholarCross Ref
- Heintz, J. and Schnorr, C. P. 1980. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the 12th annual ACM Symposium on Theory of Computing. 262--272. Google ScholarDigital Library
- Kabanets, V. and Impagliazzo, R. 2004. Derandomizing polynomial identity tests means proving circuit lower bounds. Computat. Complex. 13, 1, 1--46. Google ScholarDigital Library
- Karnin, Z., Mukhopadhyay, P., Shpilka, A., and Volkovich, I. 2010. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC). 649--658. Google ScholarDigital Library
- Karnin, Z. and Shpilka, A. 2008. Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 23rd Annual Conference on Computational Complexity (CCC). 280--291. Google ScholarDigital Library
- Karnin, Z. S. and Shpilka, A. 2009. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual Conference on Computational Complexity (CCC). 274--285. Google ScholarDigital Library
- Kayal, N. and Saraf, S. 2009. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS). 198--207. Google ScholarDigital Library
- Kayal, N. and Saxena, N. 2007. Polynomial identity testing for depth 3 circuits. Computat. Complex. 16, 2, 115--138. Google ScholarDigital Library
- Klivans, A. and Spielman, D. A. 2001. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Symposium on Theory of Computing (STOC). 216--223. Google ScholarDigital Library
- Lewin, D. and Vadhan, S. 1998. Checking polynomial identities over any field: Towards a derandomization? In Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC). 428--437. Google ScholarDigital Library
- Mulmuley, K. D. 2011. On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna. J. ACM 58, 2, 5:1--5:26. Google ScholarDigital Library
- Raz, R. 2010. Tensor-rank and lower bounds for arithmetic formulas. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). 659--666. Google ScholarDigital Library
- Saha, C., Saptharishi, R., and Saxena, N. 2011. A case of depth-3 identity testing, sparse factorization and duality. Tech. rep. TR11-021, ECCC.Google Scholar
- Saraf, S. and Volkovich, I. 2011. Black-box identity testing of depth-4 multilinear circuits. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC). 421--430. Google ScholarDigital Library
- Saxena, N. 2008. Diagonal circuit identity testing and lower bounds. In Proceedings of the 35th Annual International Colloquium on Automata, Languages and Programming (ICALP). 60--71. Google ScholarDigital Library
- Saxena, N. 2009. Progress on polynomial identity testing. EATCS, Computational Complexity Column 99, 49--79.Google Scholar
- Saxena, N. and Seshadhri, C. 2010. From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 21--29. Google ScholarDigital Library
- Saxena, N. and Seshadhri, C. 2011a. An almost optimal rank bound for depth-3 identities. SIAM J. Comp. 40, 1, 200--224. Google ScholarDigital Library
- Saxena, N. and Seshadhri, C. 2011b. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC). 431--440. Google ScholarDigital Library
- Schwartz, J. T. 1980. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 4, 701--717. Google ScholarDigital Library
- Shpilka, A. 2009. Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. Comput. 38, 6, 2130--2161. Google ScholarDigital Library
- Shpilka, A. and Volkovich, I. 2008. Read-once polynomial identity testing. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC). 507--516. Google ScholarDigital Library
- Shpilka, A. and Volkovich, I. 2009. Improved polynomial identity testing for read-once formulas. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM). 700--713. Google ScholarDigital Library
- Shpilka, A. and Yehudayoff, A. 2010. Arithmetic Circuits: A survey of recent results and open questions. Found. Trends Theoret. Comput. Scie. 5, 3--4, 207--388. Google ScholarDigital Library
- Zippel, R. 1979. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Manipulation (EUROSAM). 216--226. Google ScholarDigital Library
Index Terms
- From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits
Recommendations
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computingLet C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests if C is identically zero. Klivans & ...
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits
FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer ScienceWe 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 ...
Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
† Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011)Let $C$ be a depth-3 circuit with $n$ variables, degree $d$, and top-fanin $k$ (called ${\Sigma\Pi\Sigma}(k,d,n)$ circuits) over base field ${\mathbb{F}}$. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests ...
Comments