{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:45Z","timestamp":1787340405631,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>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 whether $C$ is identically zero. Klivans and Spielman [Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC), 2001, pp. 216--223] observed that the problem is open even when $k$ is a constant. This case has been subjected to serious scrutiny over the past few years, starting from the work of Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404--1434]. We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time ${\\mbox{\\rm poly}}(n)d^k$, regardless of the base field. The only field for which polynomial time algorithms were previously known is ${\\mathbb{F}} = {\\mathbb{Q}}$ [N. Kayal and S. Saraf, Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198--207; N. Saxena and C. Seshadhri, Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010, pp. 21--29]. This is the first blackbox algorithm for depth-3 circuits that does not use the rank-based approaches of Karnin and Shpilka [Proceedings of the 24th Annual Conference on Computational Complexity (CCC), 2009, pp. 274--285]. We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a ${\\Sigma\\Pi\\Sigma}(k,d,n)$ circuit to $k$ variables but preserves the identity structure.<\/jats:p>","DOI":"10.1137\/10848232","type":"journal-article","created":{"date-parts":[[2012,10,25]],"date-time":"2012-10-25T22:03:55Z","timestamp":1351202635000},"page":"1285-1298","source":"Crossref","is-referenced-by-count":22,"title":["Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter"],"prefix":"10.1137","volume":"41","author":[{"given":"Nitin","family":"Saxena","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,10,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. M. Adleman and H. W. Lenstra,\n                      Finding irreducible polynomials over finite fields\n                      , in Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), 1986, pp. 350-355.","DOI":"10.1145\/12130.12166"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Agrawal,\n                      Proving lower bounds via pseudo-random generators\n                      , in Proceedings of the 25th Annual Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2005, pp. 92-105.","DOI":"10.1007\/11590156_6"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M. Agrawal,\n                      Determinant versus permanent\n                      , in Proceedings of the 25th International Congress of Mathematicians (ICM), 2006, Vol. 3, pp. 985-997.","DOI":"10.4171\/022-3\/48"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena,\n                      Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-$3$ transcendence degree-k circuits\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012, pp. 599-614.","DOI":"10.1145\/2213977.2214033"},{"key":"atypb6","first-page":"149","author":"Agrawal M.","year":"2009","journal-title":"Indian Academy of Sciences"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay,\n                      Arithmetic circuits: A chasm at depth four\n                      , in Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS), 2008, pp. 67-75.","DOI":"10.1109\/FOCS.2008.32"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Anderson, D. van Melkebeek, and I. Volkovich,\n                      Derandomizing polynomial identity testing for multilinear constant-read formulae\n                      , in Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC), 2011, pp. 273-282.","DOI":"10.1109\/CCC.2011.18"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.06.003"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"M. Beecken, J. Mittmann, and N. Saxena,\n                      Algebraic independence and blackbox identity testing\n                      , in Proceedings of the 38th Annual International Colloquium on Automata, Languages and Programming (ICALP), 2011, pp. 137-148.","DOI":"10.1007\/978-3-642-22012-8_10"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and P. Tiwari,\n                      A deterministic algorithm for sparse multivariate polynominal interpolation\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 301-309.","DOI":"10.1145\/62212.62241"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Z. Chen and M. Kao,\n                      Reducing randomness via irrational numbers\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997, pp. 200-209.","DOI":"10.1145\/258533.258583"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90157-W"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2259-3"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0219073"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. Heintz and C. P. Schnorr,\n                      Testing polynomials which are easy to compute (extended abstract)\n                      , in Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), 1980, pp. 262-272.","DOI":"10.1145\/800141.804674"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Z. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich,\n                      Deterministic identity testing of depth-$4$ multilinear circuits with bounded top fan-in\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 649-658.","DOI":"10.1145\/1806689.1806779"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"Z. Karnin and A. Shpilka,\n                      Deterministic black box polynomial identity testing of depth-$3$ arithmetic circuits with bounded top fan-in\n                      , in Proceedings of the 23rd Annual Conference on Computational Complexity (CCC), 2008, pp. 280-291.","DOI":"10.1109\/CCC.2008.15"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Z. Karnin and A. Shpilka,\n                      Reconstruction of generalized depth-$3$ arithmetic circuits with bounded top fan-in\n                      , in Proceedings of the 24th Annual Conference on Computational Complexity (CCC), 2009, pp. 274-285.","DOI":"10.1109\/CCC.2009.18"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00162-X"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"N. Kayal and S. Saraf,\n                      Blackbox polynomial identity testing for depth $3$ circuits\n                      , in Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198-207.","DOI":"10.1109\/FOCS.2009.67"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. Spielman,\n                      Randomness efficient identity testing of multivariate polynomials\n                      , in Proceedings of the 33rd Symposium on Theory of Computing (STOC), 2001, pp. 216-223.","DOI":"10.1145\/380752.380801"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"D. Lewin and S. Vadhan,\n                      Checking polynomial identities over any field: Towards a derandomization?\n                      , in Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC), 1998, pp. 428-437.","DOI":"10.1145\/276698.276856"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"R. Raz,\n                      Tensor-rank and lower bounds for arithmetic formulas\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 659-666.","DOI":"10.1145\/1806689.1806780"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"atypb30","unstructured":"C. Saha, R. Saptharishi, and N. Saxena,\n                      The power of depth $2$ circuits over algebras\n                      , in Proceedings of the 29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009, pp. 371-382."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"C. Saha, R. Saptharishi, and N. Saxena,\n                      A case of depth-$3$ identity testing, sparse factorization and duality\n                      , Comput. Complexity, (2012), to appear.","DOI":"10.1007\/s00037-012-0054-4"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"S. Saraf and I. Volkovich,\n                      Black-box identity testing of depth-$4$ multilinear circuits\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 421-430.","DOI":"10.1145\/1993636.1993693"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"N. Saxena,\n                      Diagonal circuit identity testing and lower bounds\n                      , in Proceedings of the 35th Annual International Colloquium on Automata, Languages and Programming (ICALP), 2008, pp. 60-71.","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"atypb34","first-page":"49","volume":"99","author":"Saxena N.","year":"2009","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"N. Saxena and C. Seshadhri,\n                      From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-$3$ circuits\n                      , in Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010, pp. 21-29.","DOI":"10.1109\/FOCS.2010.9"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"N. Saxena and C. Seshadhri,\n                      From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-$3$ Circuits\n                      , Technical report TR10-013, ECCC, 2010.","DOI":"10.1109\/FOCS.2010.9"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"N. Saxena and C. Seshadhri,\n                      Blackbox identity testing for bounded top fanin depth-$3$ circuits: The field doesn't matter\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 431-440.","DOI":"10.1145\/1993636.1993694"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0017"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"A. Shpilka and I. Volkovich,\n                      Read-once polynomial identity testing\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2008, pp. 507-516.","DOI":"10.1145\/1374376.1374448"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"A. Shpilka and I. Volkovich,\n                      Improved polynomial identity testing for read-once formulas\n                      , in Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 2009, pp. 700-713.","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"atypb44","first-page":"91","volume":"5","author":"Werther K.","year":"1994","journal-title":"Comm. Comput."},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"R. Zippel,\n                      Probabilistic algorithms for sparse polynomials\n                      , in Proceedings of the International Symposium on Symbolic and Algebraic Manipulation (EUROSAM), 1979, pp. 216-226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/10848232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:43Z","timestamp":1787337223000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/10848232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":45,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/10848232"],"URL":"https:\/\/doi.org\/10.1137\/10848232","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}