{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:07:16Z","timestamp":1772442436658,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214033","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"599-614","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Jacobian hits circuits"],"prefix":"10.1145","author":[{"given":"Manindra","family":"Agrawal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Kanpur, Kanpur, India"}]},{"given":"Chandan","family":"Saha","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbruecken, Germany"}]},{"given":"Ramprasad","family":"Saptharishi","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai, India"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[{"name":"Hausdorff Center for Mathematics, Bonn, Germany"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_2_5_1","volume-title":"A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC), 17:105","author":"Aaronson Scott","year":"2010","unstructured":"Scott Aaronson and Dieter van Melkebeek . A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC), 17:105 , 2010 . Scott Aaronson and Dieter van Melkebeek. A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC), 17:105, 2010."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.18"},{"key":"e_1_3_2_2_7_1","first-page":"137","volume-title":"ICALP (2)","author":"Beecken Malte","year":"2011","unstructured":"Malte Beecken , Johannes Mittmann , and Nitin Saxena . Algebraic Independence and Blackbox Identity Testing . In ICALP (2) , pages 137 -- 148 , 2011 . Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing. In ICALP (2), pages 137--148, 2011."},{"key":"e_1_3_2_2_8_1","volume-title":"Algebraic Independence and Blackbox Identity Testing. CoRR, abs\/1102.2789","author":"Beecken Malte","year":"2011","unstructured":"Malte Beecken , Johannes Mittmann , and Nitin Saxena . Algebraic Independence and Blackbox Identity Testing. CoRR, abs\/1102.2789 , 2011 . Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing. CoRR, abs\/1102.2789, 2011."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90157-W"},{"key":"e_1_3_2_2_10_1","volume-title":"Partial Derivatives in Arithmetic Complexity (and beyond)","author":"Chen Xi","year":"2011","unstructured":"Xi Chen , Neeraj Kayal , and Avi Wigderson . Partial Derivatives in Arithmetic Complexity (and beyond) . Foundation and Trends in Theoretical Computer Science , 6(1--2):1--138, 2011 . Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity (and beyond). Foundation and Trends in Theoretical Computer Science, 6(1--2):1--138, 2011."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060678"},{"key":"e_1_3_2_2_13_1","first-page":"127","volume-title":"Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"Grenet Bruno","year":"2011","unstructured":"Bruno Grenet , Pascal Koiran , Natacha Portier , and Yann Strozecki . The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent . In Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , pages 127 -- 139 , 2011 . Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki. The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. In Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 127--139, 2011."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.31"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/090781231"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214050"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780595"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806779"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a010"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.15"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.18"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.67"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.36"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89518"},{"key":"e_1_3_2_2_29_1","first-page":"565","volume-title":"FCT","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . On determinants, matchings, and random algorithms . In FCT , pages 565 -- 574 , 1979 . L\u00e1szl\u00f3 Lov\u00e1sz. On determinants, matchings, and random algorithms. In FCT, pages 565--574, 1979."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1934.0015"},{"key":"e_1_3_2_2_31_1","volume-title":"TR12-014","author":"Mittmann Johannes","year":"2012","unstructured":"Johannes Mittmann , Nitin Saxena , and Peter Scheiblechner . Algebraic Independence in Positive Characteristic -- A p-adic Calculus. Electronic Colloquium on Computational Complexity , TR12-014 , 2012 . Johannes Mittmann, Nitin Saxena, and Peter Scheiblechner. Algebraic Independence in Positive Characteristic -- A p-adic Calculus. Electronic Colloquium on Computational Complexity, TR12-014, 2012."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_3_2_2_33_1","volume-title":"Matroid theory","author":"Oxley James G.","year":"1992","unstructured":"James G. Oxley . Matroid theory . Oxford University Press , 1992 . James G. Oxley. Matroid theory. Oxford University Press, 1992."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001598"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_2_37_1","first-page":"11","volume-title":"FOCS","author":"Shamir Adi","year":"1990","unstructured":"Adi Shamir . IP= PSPACE. In FOCS , pages 11 -- 15 , 1990 . Adi Shamir. IP=PSPACE. In FOCS, pages 11--15, 1990."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.20"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.9"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993694"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3158"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374448"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"e_1_3_2_2_44_1","first-page":"408","volume-title":"ICALP (1)","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Ilya Volkovich . On the relation between polynomial identity testing and finding variable disjoint factors . In ICALP (1) , pages 408 -- 419 , 2010 . Amir Shpilka and Ilya Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In ICALP (1), pages 408--419, 2010."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993693"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.36"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214033","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214033"}},"subtitle":["hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits"],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":51,"alternative-id":["10.1145\/2213977.2214033","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214033","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}