{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T21:20:47Z","timestamp":1767993647646,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,25]],"date-time":"2015-04-25T00:00:00Z","timestamp":1429920000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00037-015-0097-4","type":"journal-article","created":{"date-parts":[[2015,4,24]],"date-time":"2015-04-24T09:18:12Z","timestamp":1429867092000},"page":"695-776","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Deterministic polynomial identity tests for multilinear bounded-read formulae"],"prefix":"10.1007","volume":"24","author":[{"given":"Matthew","family":"Anderson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,25]]},"reference":[{"issue":"1","key":"97_CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.4086\/toc.2011.v007a012","volume":"7","author":"S. Aaronson","year":"2011","unstructured":"Aaronson S., van Melkebeek D. (2011) On Circuit Lower Bounds from Derandomization. Theory of Computing 7(1): 177\u2013184","journal-title":"Theory of Computing"},{"key":"97_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal (2003). On derandomizing tests for certain polynomial identities. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 355\u2013359. ISBN 0769518796. ISSN 1093-0159.","DOI":"10.1109\/CCC.2003.1214434"},{"issue":"4","key":"97_CR3","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M. Agrawal","year":"2003","unstructured":"Agrawal M., Biswas S. (2003) Primality and identity testing via chinese remaindering. Journal of the ACM 50(4): 429\u2013443","journal-title":"Journal of the ACM"},{"key":"97_CR4","doi-asserted-by":"crossref","unstructured":"M. Agrawal, Saha, R. Saptharishi & N. Saxena (2012). Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 599\u2013614.","DOI":"10.1145\/2213977.2214033"},{"key":"97_CR5","doi-asserted-by":"crossref","unstructured":"M. Agrawal & V. Vinay (2008). Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual Symposium on Foundations of Computer Science, 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"97_CR6","doi-asserted-by":"crossref","unstructured":"M. Anderson, D. van Melkebeek & I. Volkovich (2011). Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 273\u2013282.","DOI":"10.1109\/CCC.2011.18"},{"issue":"4","key":"97_CR7","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.ic.2009.06.003","volume":"208","author":"V. Arvind","year":"2010","unstructured":"Arvind V., Mukhopadhyay P. (2010) The ideal membership problem and polynomial identity testing. Information and Computation 208(4): 351\u2013363","journal-title":"Information and Computation"},{"key":"97_CR8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"Baur W., Strassen V. (1983) The complexity of partial derivatives. Theoretical Computer Science 22: 317\u2013330","journal-title":"Theoretical Computer Science"},{"key":"97_CR9","doi-asserted-by":"crossref","unstructured":"M. Ben-Or & P. Tiwari (1988). A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 301\u2013309. ISBN 0897912640.","DOI":"10.1145\/62212.62241"},{"issue":"3","key":"97_CR10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.ipl.2008.09.029","volume":"109","author":"M. Bl\u00e4ser","year":"2009","unstructured":"Bl\u00e4ser M., Hardt M., Lipton R., Vishnoi N. (2009) Deterministically testing sparse polynomial identities of unbounded degree. Information Processing Letters 109(3): 187\u2013192","journal-title":"Information Processing Letters"},{"issue":"4","key":"97_CR11","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R. DeMillo","year":"1978","unstructured":"DeMillo R., Lipton R. (1978) A probabilistic remark on algebraic program testing. Information Processing Letters 7(4): 193\u2013195","journal-title":"Information Processing Letters"},{"key":"97_CR12","doi-asserted-by":"crossref","unstructured":"Z. Dvir & A. Shpilka (2007). Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM Journal on Computing 36(5), 1404\u20131434. ISSN 0097-5397.","DOI":"10.1137\/05063605X"},{"issue":"4","key":"97_CR13","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1137\/080735850","volume":"39","author":"Z. Dvir","year":"2009","unstructured":"Dvir Z., Shpilka A., Yehudayoff A. (2009) Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing 39(4): 1279\u20131293","journal-title":"SIAM Journal on Computing"},{"key":"97_CR14","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal & R. Saptharishi (2013). Arithmetic circuits: A chasm at depth three. Technical Report 26, Electronic Colloquium on Computational Complexity.","DOI":"10.1109\/FOCS.2013.68"},{"key":"97_CR15","unstructured":"M. Jansen, Y. Qiao & J. Sarma (2009). Deterministic Identity Testing of Read-Once Algebraic Branching Programs. Technical Report abs\/0912.2565, CoRR."},{"issue":"1","key":"97_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets V., Impagliazzo R. (2004) Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1): 1\u201346","journal-title":"Computational Complexity"},{"issue":"6","key":"97_CR17","doi-asserted-by":"crossref","first-page":"2114","DOI":"10.1137\/110824516","volume":"42","author":"Z. Karnin","year":"2013","unstructured":"Karnin Z., Mukhopadhyay P., Shpilka A., Volkovich I. (2013) Deterministic Identity Testing of Depth 4 Multilinear Circuits with Bounded Top Fan-In. SIAM Journal on Computing 42(6): 2114\u20132131","journal-title":"SIAM Journal on Computing"},{"key":"97_CR18","doi-asserted-by":"crossref","unstructured":"Z. Karnin & A. Shpilka (2008). Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 280\u2013291.","DOI":"10.1109\/CCC.2008.15"},{"key":"97_CR19","doi-asserted-by":"crossref","unstructured":"N. Kayal & S. Saraf (2009). Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 198\u2013207.","DOI":"10.1109\/FOCS.2009.67"},{"issue":"1","key":"97_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00037-011-0019-z","volume":"21","author":"J. Kinne","year":"2012","unstructured":"Kinne J., van Melkebeek D., Shaltiel R. (2012) Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity 21(1): 3\u201361","journal-title":"Computational Complexity"},{"issue":"10","key":"97_CR21","doi-asserted-by":"crossref","first-page":"185","DOI":"10.4086\/toc.2006.v002a010","volume":"2","author":"A. Klivans","year":"2006","unstructured":"Klivans A., Shpilka A. (2006) Learning restricted models of arithmetic circuits. Theory of computing 2(10): 185\u2013206","journal-title":"Theory of computing"},{"key":"97_CR22","doi-asserted-by":"crossref","unstructured":"A. Klivans & D. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"97_CR23","first-page":"565","volume":"79","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L. (1979) On determinants, matchings and random algorithms. In Fundamentals of Computation Theory, volume 79: 565\u2013574","journal-title":"In Fundamentals of Computation Theory, volume"},{"key":"97_CR24","doi-asserted-by":"crossref","first-page":"4241","DOI":"10.1155\/S1073792804142566","volume":"79","author":"T. Mignon","year":"2004","unstructured":"Mignon T., Ressayre N. (2004) A Quadratic Bound for the Determinant and Permanent Problem. International Mathematics Research Notices 79: 4241\u20134253","journal-title":"International Mathematics Research Notices"},{"key":"97_CR25","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N. Nisan","year":"1996","unstructured":"Nisan N., Wigderson A. (1996) Lower bound on arithmetic circuits via partial derivatives. Computational Complexity 6: 217\u2013234","journal-title":"Computational Complexity"},{"key":"97_CR26","doi-asserted-by":"crossref","unstructured":"R. Raz & A. Yehudayoff (2008). Lower Bounds and Separations for Constant Depth Multilinear Circuits. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 128\u2013139.","DOI":"10.1109\/CCC.2008.8"},{"key":"97_CR27","doi-asserted-by":"crossref","unstructured":"S. Saraf & I. Volkovich (2011). Black-Box Identity Testing of Depth-4 Multilinear Circuits. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 421\u2013430.","DOI":"10.1145\/1993636.1993693"},{"key":"97_CR28","doi-asserted-by":"crossref","unstructured":"N. Saxena (2008). Diagonal circuit identity testing and lower bounds. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, 60\u201371.","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"97_CR29","first-page":"49","volume":"99","author":"N. Saxena","year":"2009","unstructured":"Saxena N. (2009) Progress on polynomial identity testing. Bulletin of the EATCS 99: 49\u201379","journal-title":"Bulletin of the EATCS"},{"key":"97_CR30","doi-asserted-by":"crossref","unstructured":"N. Saxena & C. Seshadhri (2009). An almost optimal rank bound for depth-3 identities. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 137\u2013148.","DOI":"10.1109\/CCC.2009.20"},{"key":"97_CR31","doi-asserted-by":"crossref","unstructured":"N. Saxena & C. Seshadhri (2010). From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, 21\u201329.","DOI":"10.1109\/FOCS.2010.9"},{"issue":"5","key":"97_CR32","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1137\/10848232","volume":"41","author":"N. Saxena","year":"2012","unstructured":"Saxena N., Seshadhri C. (2012) Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn\u2019t Matter. SIAM Journal on Computing 41(5): 1285\u20131298","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"97_CR33","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz J. (1980) Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27(4): 701\u2013717","journal-title":"Journal of the ACM"},{"key":"97_CR34","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2008). Read-once polynomial identity testing. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 507\u2013516.","DOI":"10.1145\/1374376.1374448"},{"key":"97_CR35","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2009). Improved polynomial identity testing for read-once formulas. In Proceedings of the 13th International Workshop on Randomization and Computation, 700\u2013713.","DOI":"10.1007\/978-3-642-03685-9_52"},{"issue":"1","key":"97_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"A. Shpilka","year":"2001","unstructured":"Shpilka A., Wigderson A. (2001) Depth-3 Arithmetic Circuits over Fields of Characteristic Zero. Computational Complexity 10(1): 1\u201327","journal-title":"Computational Complexity"},{"key":"97_CR37","unstructured":"A. Shpilka & A. Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3\u20134), 207\u2013388."},{"key":"97_CR38","doi-asserted-by":"crossref","unstructured":"R. Zippel (1979). Probabilistic algorithms for sparse polynomials. Symbolic and Algebraic Computation 216\u2013226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0097-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0097-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0097-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0097-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,25]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["97"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0097-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,25]]}}}