{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:44Z","timestamp":1787340224801,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We study the problem of polynomial identity testing for depth-3 circuits of degree d and top fanin k. The rank of any such identity is essentially the minimum number of independent variables present. Small bounds on this quantity imply fast deterministic identity testers for these circuits. Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404\u20131434] initiated the study of the rank and showed that any depth-3 identity (barring some uninteresting corner cases) has a rank of $2^{O(k^2)}(\\log d)^{k-2}$. We show that the rank of a depth-3 identity is at most $O(k^3\\log d)$. This bound is almost tight, since we also provide an identity of rank $\\Omega(k\\log d)$. Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka [Z. Karnin and A. Shpilka, in Proceedings of the 23rd CCC, 2008, pp. 280\u2013291]. Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits: the rank of linear factors of a simple, minimal, and nonzero depth-3 circuit (over any field) is at most $O(k^3\\log d)$. The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these ideas may lead to the goal of a deterministic polynomial time identity test for these circuits.<\/jats:p>","DOI":"10.1137\/090770679","type":"journal-article","created":{"date-parts":[[2011,2,24]],"date-time":"2011-02-24T18:32:14Z","timestamp":1298572334000},"page":"200-224","source":"Crossref","is-referenced-by-count":20,"title":["An Almost Optimal Rank Bound for Depth-3 Identities"],"prefix":"10.1137","volume":"40","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":[[2011,2,24]]},"reference":[{"key":"R1","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) Conference, Hyderabad, India, 2005, pp. 92\u2013105.","DOI":"10.1007\/11590156_6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay,\n                      Arithmetic circuits: A chasm at depth four\n                      , in Proceedings of FOCS, IEEE, Washington, DC, 2008, pp. 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"V. Arvind and P. Mukhopadhyaya,\n                      The monomial ideal membership problem and polynomial identity testing\n                      , in Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), Sendai, Japan, 2007, pp. 800\u2013811.","DOI":"10.1007\/978-3-540-77120-3_69"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798341600"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"R8","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), IEEE, Washington, DC, 2008, pp. 280\u2013291.","DOI":"10.1109\/CCC.2008.15"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"N. Kayal and S. Saraf,\n                      Blackbox Polynomial Identity Testing for Depth 3 Circuits\n                      , Technical report TR09-032, ECCC, 2009.","DOI":"10.1109\/FOCS.2009.67"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. Spielman,\n                      Randomness efficient identity testing of multivariate polynomials\n                      , in Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC), ACM, New York, 2001, pp. 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"R12","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 Theory of Computing (STOC), ACM, New York, 1998, pp. 428\u2013437.","DOI":"10.1145\/276698.276856"},{"key":"R13","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), Reykjavik, Iceland, 2008, pp. 60\u201371.","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"N. Saxena and C. Seshadhri,\n                      An almost optimal rank bound for depth-3 identities\n                      , in Proceedings of the 24th Annual Conference on Computational Complexity (CCC), IEEE, Washington, DC, 2009, pp. 137\u2013148.","DOI":"10.1109\/CCC.2009.20"},{"key":"R15","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 IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2010, pp. 21\u201329.","DOI":"10.1109\/FOCS.2010.9"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"R17","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), Berkeley, CA, 2009, pp. 700\u2013713.","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. Zippel,\n                      Probabilistic algorithms for sparse polynomials\n                      , in Symbolic and Algebraic Computation, Lecture Notes in Comput. Sci. 72, Springer, New York, 1979, pp. 216\u2013226.","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\/090770679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:46Z","timestamp":1787336746000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090770679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090770679"],"URL":"https:\/\/doi.org\/10.1137\/090770679","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}