{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:03:47Z","timestamp":1767978227148,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,5,27]],"date-time":"2015-05-27T00:00:00Z","timestamp":1432684800000},"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,9]]},"DOI":"10.1007\/s00037-015-0105-8","type":"journal-article","created":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T03:48:14Z","timestamp":1432612094000},"page":"477-532","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Read-once polynomial identity testing"],"prefix":"10.1007","volume":"24","author":[{"given":"Amir","family":"Shpilka","sequence":"first","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,5,27]]},"reference":[{"key":"105_CR1","doi-asserted-by":"crossref","unstructured":"M. Agrawal (2005). Proving Lower Bounds Via Pseudo-random Generators. In Proceedings of the 25th FSTTCS, volume 3821 of LNCS, 92\u2013105.","DOI":"10.1007\/11590156_6"},{"key":"105_CR2","unstructured":"M. Agrawal, R. Gurjar, A. Korwar & N. Saxena (2014). Hitting-sets for ROABP and Sum of Set-Multilinear circuits. CoRR abs\/1406.7535 ."},{"issue":"2","key":"105_CR3","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal M., Kayal N., Saxena N. (2004) PRIMES is in P. Annals of Mathematics 160(2): 781\u2013793","journal-title":"Annals of Mathematics"},{"key":"105_CR4","doi-asserted-by":"crossref","unstructured":"M. Agrawal, C. 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 (STOC), 599\u2013614.","DOI":"10.1145\/2213977.2214033"},{"key":"105_CR5","doi-asserted-by":"crossref","unstructured":"M. Agrawal, C. Saha & N. Saxena (2013). Quasi-polynomial hitting-set for set-depth- formulas. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 321\u2013330.","DOI":"10.1145\/2488608.2488649"},{"key":"105_CR6","doi-asserted-by":"crossref","unstructured":"M. Agrawal & V. Vinay (2008). Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"105_CR7","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N. Alon","year":"1999","unstructured":"Alon N. (1999) Combinatorial Nullstellensatz. Combinatorics, Probability and Computing 8: 7\u201329","journal-title":"Combinatorics, Probability and Computing"},{"key":"105_CR8","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, (CCC), 273\u2013282. Full version at http:\/\/eccc.hpi-web.de\/report\/2010\/188 .","DOI":"10.1109\/CCC.2011.18"},{"issue":"1","key":"105_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/138027.138061","volume":"40","author":"D. Angluin","year":"1993","unstructured":"Angluin D., Hellerstein L., Karpinski M. (1993) Learning read-once formulas with queries. J. ACM 40(1): 185\u2013210","journal-title":"J. ACM"},{"issue":"4","key":"105_CR10","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 Monomial Ideal Membership Problem and Polynomial Identity Testing. Information and Computation 208(4): 351\u2013363","journal-title":"Information and Computation"},{"key":"105_CR11","unstructured":"M. Ben-Or & P. Tiwari (1988). A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 301\u2013309."},{"issue":"1","key":"105_CR12","first-page":"112","volume":"56","author":"D. Bshouty","year":"1998","unstructured":"Bshouty D., Bshouty N. H. (1998) On Interpolating Arithmetic Read-Once Formulas with Exponentiation. JCSS 56(1): 112\u2013124","journal-title":"JCSS"},{"issue":"2","key":"105_CR13","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S009753979528812X","volume":"27","author":"N. H. Bshouty","year":"1998","unstructured":"Bshouty N. H., Cleve R. (1998) Interpolating arithmetic read-once formulas in parallel. SIAM J. on Computing 27(2): 401\u2013413","journal-title":"SIAM J. on Computing"},{"key":"105_CR14","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, T. R. Hancock & L. Hellerstein (1995a). Learning Arithmetic Read-Once Formulas. SIAM J. on Computing 24(4), 706\u2013735.","DOI":"10.1137\/S009753979223664X"},{"key":"105_CR15","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, T. R. Hancock & L. Hellerstein (1995b). Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates. JCSS 50, 521\u2013542.","DOI":"10.1006\/jcss.1995.1042"},{"key":"105_CR16","doi-asserted-by":"crossref","unstructured":"R. A. DeMillo & R. J. Lipton (1978). A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4), 193\u2013195.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"105_CR17","doi-asserted-by":"crossref","unstructured":"Z. Dvir & A. Shpilka (2006). Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. on Computing 36(5), 1404\u20131434.","DOI":"10.1137\/05063605X"},{"key":"105_CR18","doi-asserted-by":"crossref","unstructured":"Z. Dvir, A. Shpilka & A. Yehudayoff (2009). Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. on Computing 39(4), 1279\u20131293.","DOI":"10.1137\/080735850"},{"key":"105_CR19","doi-asserted-by":"crossref","unstructured":"M. Forbes, R. Saptharishi & A. Shpilka (2014). Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 867\u2013875. Full version at http:\/\/eccc.hpi-web.de\/report\/2013\/132 .","DOI":"10.1145\/2591796.2591816"},{"key":"105_CR20","doi-asserted-by":"crossref","unstructured":"M. Forbes & A. Shpilka (2012). On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 163\u2013171.","DOI":"10.1145\/2213977.2213995"},{"key":"105_CR21","unstructured":"M. Forbes & A. Shpilka (2013). Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 243\u2013252. Full version at http:\/\/eccc.hpi-web.de\/report\/2012\/115 ."},{"key":"105_CR22","unstructured":"T. R. Hancock & L. Hellerstein (1991). Learning read-once formulas over fields and extended bases. In Proceedings of the 4th Annual Workshop on Computational Learning Theory (COLT), 326\u2013336."},{"key":"105_CR23","doi-asserted-by":"crossref","unstructured":"J. Heintz & C. P. Schnorr (1980). Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), 262\u2013272.","DOI":"10.1145\/800141.804674"},{"key":"105_CR24","unstructured":"M. Jansen, Y. Qiao & J. Sarma (2009). Deterministic Identity Testing of Read-Once Algebraic Branching Programs. CoRR abs\/0912.2565 ."},{"key":"105_CR25","unstructured":"M. Jansen, Y. Qiao & J. Sarma (2010). Deterministic Black-Box Identity Testing \u03c0-Ordered Algebraic Branching Programs. In FSTTCS, 296\u2013307."},{"key":"105_CR26","doi-asserted-by":"crossref","unstructured":"V. Kabanets & R. Impagliazzo (2004). Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"105_CR27","doi-asserted-by":"crossref","unstructured":"M. Karchmer, N. Linial, I. Newman, M. E. Saks & A. Wigderson (1993). Combinatorial characterization of read-once formulae. Discrete Mathematics 114(1-3), 275\u2013282.","DOI":"10.1016\/0012-365X(93)90372-Z"},{"key":"105_CR28","doi-asserted-by":"crossref","unstructured":"Z. S. Karnin, P. Mukhopadhyay, A. Shpilka & I. Volkovich (2013). Deterministic Identity Testing of Depth 4 Multilinear Circuits with Bounded Top Fan-In. SIAM J. on Computing 42(6), 2114\u20132131.","DOI":"10.1137\/110824516"},{"key":"105_CR29","unstructured":"Z. S. Karnin & A. Shpilka (2009). Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), 274\u2013285. Full version at http:\/\/www.cs.technion.ac.il\/~shpilka\/publications\/KarninShpilka09.pdf ."},{"key":"105_CR30","doi-asserted-by":"crossref","unstructured":"Z. S. Karnin & A. Shpilka (2011). Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31(3), 333\u2013364.","DOI":"10.1007\/s00493-011-2537-3"},{"key":"105_CR31","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 (FOCS), 198\u2013207. Full version at http:\/\/eccc.hpi-web.de\/report\/2009\/032 .","DOI":"10.1109\/FOCS.2009.67"},{"key":"105_CR32","doi-asserted-by":"crossref","unstructured":"N. Kayal & N. Saxena (2007). Polynomial Identity Testing for Depth 3 Circuits. Computational Complexity 16(2), 115\u2013138.","DOI":"10.1007\/s00037-007-0226-9"},{"key":"105_CR33","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 (STOC), 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"105_CR34","unstructured":"R. J. Lipton & N. K. Vishnoi (2003). Deterministic identity testing for multivariate polynomials. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 756\u2013760."},{"key":"105_CR35","unstructured":"L. Lovasz (1979). On determinants, matchings, and random algorithms. In Fundamentals of Computing Theory, L. Budach, editor. Akademia-Verlag."},{"key":"105_CR36","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, U. Vazirani & V. Vazirani (1987). Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113.","DOI":"10.1007\/BF02579206"},{"issue":"1","key":"105_CR37","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2006.v002a006","volume":"2","author":"R. Raz","year":"2006","unstructured":"Raz R. (2006) Separation of Multilinear Circuit and Formula Size. Theory of Computing 2(1): 121\u2013135","journal-title":"Theory of Computing"},{"key":"105_CR38","doi-asserted-by":"crossref","unstructured":"R. Raz (2009). Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2).","DOI":"10.1145\/1502793.1502797"},{"key":"105_CR39","doi-asserted-by":"crossref","unstructured":"R. Raz & A. Shpilka (2005). Deterministic Polynomial Identity Testing in Non Commutative Models. Computational Complexity 14(1), 1\u201319.","DOI":"10.1007\/s00037-005-0188-8"},{"key":"105_CR40","doi-asserted-by":"crossref","unstructured":"R. Raz, A. Shpilka & A. Yehudayoff (2008). A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. on Computing 38(4), 1624\u20131647.","DOI":"10.1137\/070707932"},{"issue":"2","key":"105_CR41","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"R. Raz","year":"2009","unstructured":"Raz R., Yehudayoff A. (2009) Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity 18(2): 171\u2013207","journal-title":"Computational Complexity"},{"key":"105_CR42","unstructured":"S. Saraf & I. Volkovich (2011). Blackbox Identity Testing for Depth-4 Multilinear Circuits. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 421\u2013430. Full version at http:\/\/eccc.hpi-web.de\/report\/2011\/046 ."},{"key":"105_CR43","doi-asserted-by":"crossref","unstructured":"N. Saxena (2008). Diagonal Circuit Identity Testing and Lower Bounds. In Automata, Languages and Programming, 35th International Colloquium, 60\u201371. Full version at http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-124\/index.html .","DOI":"10.1007\/978-3-540-70575-8_6"},{"issue":"1","key":"105_CR44","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/090770679","volume":"40","author":"N. Saxena","year":"2011","unstructured":"Saxena N., Seshadhri C. (2011) An Almost Optimal Rank Bound for Depth-3 Identities. SIAM J. Comput. 40(1): 200\u2013224","journal-title":"SIAM J. Comput."},{"key":"105_CR45","doi-asserted-by":"crossref","unstructured":"N. Saxena & C. Seshadhri (2012). Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn\u2019t Matter. SIAM J. Comput. 41(5), 1285\u20131298.","DOI":"10.1137\/10848232"},{"key":"105_CR46","doi-asserted-by":"crossref","unstructured":"N. Saxena & C. Seshadhri (2013). From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM 60(5), 33.","DOI":"10.1145\/2528403"},{"key":"105_CR47","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz (1980). Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717.","DOI":"10.1145\/322217.322225"},{"issue":"6","key":"105_CR48","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"A. Shpilka","year":"2009","unstructured":"Shpilka A. (2009) Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. on Computing 38(6): 2130\u20132161","journal-title":"SIAM J. on Computing"},{"key":"105_CR49","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 (STOC), 507\u2013516.","DOI":"10.1145\/1374376.1374448"},{"key":"105_CR50","unstructured":"A. Shpilka & I. Volkovich (2009). Improved Polynomial Identity Testing for Read-Once Formulas. In APPROX-RANDOM, 700\u2013713. Full version at http:\/\/eccc.hpi-web.de\/report\/2010\/011 ."},{"key":"105_CR51","doi-asserted-by":"crossref","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-4), 207\u2013388.","DOI":"10.1561\/0400000039"},{"key":"105_CR52","doi-asserted-by":"crossref","unstructured":"R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on 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-0105-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0105-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0105-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,25]],"date-time":"2019-08-25T10:56:25Z","timestamp":1566730585000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0105-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,27]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["105"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0105-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,27]]}}}