{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T13:36:04Z","timestamp":1776692164536,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_52","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"700-713","source":"Crossref","is-referenced-by-count":29,"title":["Improved Polynomial Identity Testing for Read-Once Formulas"],"prefix":"10.1007","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","reference":[{"key":"52_CR1","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/11590156_6","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"M. Agrawal","year":"2005","unstructured":"Agrawal, M.: Proving lower bounds via pseudo-random generators. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 92\u2013105. Springer, Heidelberg (2005)"},{"issue":"4","key":"52_CR2","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M. Agrawal","year":"2003","unstructured":"Agrawal, M., Biswas, S.: Primality and identity testing via chinese remaindering. JACM\u00a050(4), 429\u2013443 (2003)","journal-title":"JACM"},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: A chasm at depth four. In: Proceedings of the 49th FOCS, pp. 67\u201375 (2008)","DOI":"10.1109\/FOCS.2008.32"},{"key":"52_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/978-3-540-77120-3_69","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"2007","unstructured":"Arvind, V., Mukhopadhyay, P.: The monomial ideal membership problem and polynomial identity testing. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 800\u2013811. Springer, Heidelberg (2007)"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings of the 20th STOC, pp. 301\u2013309 (1988)","DOI":"10.1145\/62212.62241"},{"issue":"1","key":"52_CR6","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcss.1997.1550","volume":"56","author":"D. Bshouty","year":"1998","unstructured":"Bshouty, D., Bshouty, N.H.: On interpolating arithmetic read-once formulas with exponentiation. J. of Computer and System Sciences\u00a056(1), 112\u2013124 (1998)","journal-title":"J. of Computer and System Sciences"},{"issue":"4","key":"52_CR7","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1137\/S009753979223664X","volume":"24","author":"N.H. Bshouty","year":"1995","unstructured":"Bshouty, N.H., Hancock, T.R., Hellerstein, L.: Learning arithmetic read-once formulas. SICOMP\u00a024(4), 706\u2013735 (1995)","journal-title":"SICOMP"},{"key":"52_CR8","doi-asserted-by":"crossref","unstructured":"Chen, Z., Kao, M.: Reducing randomness via irrational numbers. In: Proceedings of the 29th STOC, pp. 200\u2013209 (1997)","DOI":"10.1145\/258533.258583"},{"issue":"5","key":"52_CR9","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z. Dvir","year":"2006","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SICOMP\u00a036(5), 1404\u20131434 (2006)","journal-title":"SICOMP"},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Shpilka, A., Yehudayoff, A.: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. In: Proceedings of the 40th STOC, pp. 741\u2013748 (2008)","DOI":"10.1145\/1374376.1374482"},{"key":"52_CR11","doi-asserted-by":"crossref","unstructured":"Hancock, T.R., Hellerstein, L.: Learning read-once formulas over fields and extended bases. In: Proceedings of the 4th COLT, pp. 326\u2013336 (1991)","DOI":"10.1016\/B978-1-55860-213-7.50033-X"},{"issue":"1-2","key":"52_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity\u00a013(1-2), 1\u201346 (2004)","journal-title":"Computational Complexity"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Karnin, Z.S., Shpilka, A.: Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in. In: Proceedings of the 23rd CCC, pp. 280\u2013291 (2008)","DOI":"10.1109\/CCC.2008.15"},{"issue":"2","key":"52_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","volume":"16","author":"N. Kayal","year":"2007","unstructured":"Kayal, N., Saxena, N.: Polynomial identity testing for depth 3 circuits. Computational Complexity\u00a016(2), 115\u2013138 (2007)","journal-title":"Computational Complexity"},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of the 33rd STOC, pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"Lewin, D., Vadhan, S.: Checking polynomial identities over any field: Towards a derandomization? In: Proceedings of the 30th STOC, pp. 428\u2013437 (1998)","DOI":"10.1145\/276698.276856"},{"key":"52_CR17","unstructured":"Lipton, R.J., Vishnoi, N.K.: Deterministic identity testing for multivariate polynomials. In: Proceedings of the 14th SODA, pp. 756\u2013760 (2003)"},{"key":"52_CR18","unstructured":"Raz, R.: Multilinear NC\n                           1\u2009\u2260 Multilinear NC\n                           2. In: Proceedings of the 45th FOCS, pp. 344\u2013351 (2004)"},{"key":"52_CR19","doi-asserted-by":"crossref","unstructured":"Raz, R.: Extractors with weak random seeds. In: Proceedings of the 37th STOC, pp. 11\u201320 (2005)","DOI":"10.1145\/1060590.1060593"},{"issue":"1","key":"52_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non commutative models. Computational Complexity\u00a014(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"issue":"4","key":"52_CR21","doi-asserted-by":"crossref","first-page":"1624","DOI":"10.1137\/070707932","volume":"38","author":"R. Raz","year":"2008","unstructured":"Raz, R., Shpilka, A., Yehudayoff, A.: A lower bound for the size of syntactically multilinear arithmetic circuits. SICOMP\u00a038(4), 1624\u20131647 (2008)","journal-title":"SICOMP"},{"key":"52_CR22","doi-asserted-by":"crossref","unstructured":"Raz, R., Yehudayoff, A.: Lower bounds and separations for constant depth multilinear circuits. In: 40th CCC, pp. 128\u2013139 (2008)","DOI":"10.1109\/CCC.2008.8"},{"key":"52_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-540-70575-8_6","volume-title":"Automata, Languages and Programming","author":"N. Saxena","year":"2008","unstructured":"Saxena, N.: Diagonal circuit identity testing and lower bounds. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 60\u201371. Springer, Heidelberg (2008)"},{"key":"52_CR24","doi-asserted-by":"crossref","unstructured":"Saxena, N., Seshadhri, C.: An almost optimal rank bound for depth-3 identities. CoRR, abs\/0811.3161 (2008)","DOI":"10.1109\/CCC.2009.20"},{"issue":"4","key":"52_CR25","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. JACM\u00a027(4), 701\u2013717 (1980)","journal-title":"JACM"},{"issue":"6","key":"52_CR26","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"A. Shpilka","year":"2009","unstructured":"Shpilka, A.: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SICOMP\u00a038(6), 2130\u20132161 (2009)","journal-title":"SICOMP"},{"key":"52_CR27","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Volkovich, I.: Read-once polynomial identity testing. In: Proceedings of the 40th STOC, pp. 507\u2013516 (2008)","DOI":"10.1145\/1374376.1374448"},{"key":"52_CR28","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and algebraic computation, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:15:44Z","timestamp":1558282544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}