{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T11:23:54Z","timestamp":1787311434562,"version":"build-2736575974"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Early Career Program at Sandia National Labs"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>\n                    We study the problem of identity testing for depth-3 circuits of top fanin\n                    <jats:italic>k<\/jats:italic>\n                    and degree\n                    <jats:italic>d<\/jats:italic>\n                    . We give a new structure theorem for such identities that improves the known deterministic\n                    <jats:italic>d<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>k<\/jats:italic>\n                    <\/jats:sup>\n                    <jats:sup>\n                      <jats:italic>O<\/jats:italic>\n                      (\n                      <jats:italic>k<\/jats:italic>\n                      )\n                    <\/jats:sup>\n                    -time blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes\n                    <jats:italic>d<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>O<\/jats:italic>\n                      (\n                      <jats:italic>k<\/jats:italic>\n                      <jats:sup>2<\/jats:sup>\n                      )\n                    <\/jats:sup>\n                    -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].\n                  <\/jats:p>\n                  <jats:p>\n                    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\n                    <jats:italic>nucleus identity<\/jats:italic>\n                    that contains most of the \u201ccomplexity\u201d 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\n                    <jats:italic>Sylvester-Gallai rank bound<\/jats:italic>\n                    , 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).\n                  <\/jats:p>","DOI":"10.1145\/2528403","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T11:29:17Z","timestamp":1382527757000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["From sylvester-gallai configurations to rank bounds"],"prefix":"10.1145","volume":"60","author":[{"given":"Nitin","family":"Saxena","sequence":"first","affiliation":[{"name":"Hausdorff Center for Mathematics, Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 25th International Congress of Mathematicians (ICM).","volume":"3","author":"Agrawal M.","year":"2006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"e_1_2_1_4_1","unstructured":"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\/.  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\/."},{"key":"e_1_2_1_5_1","unstructured":"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.  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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.06.003"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 38th Annual International Colloquium on Automata, Languages and Programming (ICALP). 137--148","author":"Beecken M."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.28"},{"key":"e_1_2_1_11_1","first-page":"11","article-title":"Flats associated with finite sets in Pd","volume":"15","author":"Bonnice W.","year":"1967","journal-title":"Niew. Arch. Wisk."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02112289"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798341600"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1226-7"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 17th Annual Computational Complexity Conference (CCC). 175--183","author":"Goldreich O."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10758"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806779"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.15"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.18"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.67"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276856"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944346"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806780"},{"key":"e_1_2_1_30_1","unstructured":"Saha C. Saptharishi R. and Saxena N. 2011. A case of depth-3 identity testing sparse factorization and duality. Tech. rep. TR11-021 ECCC.  Saha C. Saptharishi R. and Saxena N. 2011. A case of depth-3 identity testing sparse factorization and duality. Tech. rep. TR11-021 ECCC."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993693"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"e_1_2_1_33_1","first-page":"49","article-title":"Progress on polynomial identity testing. EATCS","volume":"99","author":"Saxena N.","year":"2009","journal-title":"Computational Complexity Column"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993694"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/070694879"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374448"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2528403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:28:44Z","timestamp":1750217324000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528403"}},"subtitle":["Improved blackbox identity test for depth-3 circuits"],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2528403"],"URL":"https:\/\/doi.org\/10.1145\/2528403","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2012-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}