{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T23:11:54Z","timestamp":1768173114675,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2011,5]]},"DOI":"10.1007\/s00493-011-2537-3","type":"journal-article","created":{"date-parts":[[2011,9,7]],"date-time":"2011-09-07T08:33:51Z","timestamp":1315384431000},"page":"333-364","source":"Crossref","is-referenced-by-count":21,"title":["Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in"],"prefix":"10.1007","volume":"31","author":[{"given":"Zohar S.","family":"Karnin","sequence":"first","affiliation":[]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,8]]},"reference":[{"issue":"4","key":"2537_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M. Agrawal","year":"2003","unstructured":"M. Agrawal and S. Biswas: Primality and identity testing via chinese remaindering, JACM, 50(4) (2003), 429\u2013443.","journal-title":"JACM"},{"key":"2537_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal: Proving lower bounds via pseudo-random generators, In Proceedings of the 25th FSTTCS, volume 3821 of LNCS, pages 92\u2013105, 2005.","DOI":"10.1007\/11590156_6"},{"key":"2537_CR3","doi-asserted-by":"crossref","unstructured":"V. Arvind and P. Mukhopadhyay: The monomial ideal membership problem and polynomial identity testing, In Proceedings of the 18th ISAAC, pages 800\u2013811, 2007.","DOI":"10.1007\/978-3-540-77120-3_69"},{"key":"2537_CR4","doi-asserted-by":"crossref","unstructured":"M. Ben-or and P. Tiwari: A deterministic algorithm for sparse multivariate poly-nominal interpolation, In Proceedings of the 20th Annual STOC, pages 301\u2013309, 1988.","DOI":"10.1145\/62212.62241"},{"issue":"5","key":"2537_CR5","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/S0097539793250330","volume":"24","author":"S. Chari","year":"1995","unstructured":"S. Chari, P. Rohatgi, and A. Srinivasan: Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. on Computing, 24(5) (1995), 1036\u20131050.","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"2537_CR6","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1137\/S0097539798341600","volume":"29","author":"Z. Chen","year":"2000","unstructured":"Z. Chen and M. Kao: Reducing randomness via irrational numbers, SIAM J. on Computing, 29(4) (2000), 1247\u20131256.","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"2537_CR7","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0304-3975(91)90157-W","volume":"84","author":"M. Clausen","year":"1991","unstructured":"M. Clausen, A. W. M. Dress, J. Grabmeier, and M. Karpinski: On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields, Theoretical Computer Science, 84(2) (1991), 151\u2013164.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"2537_CR8","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z. Dvir","year":"2006","unstructured":"Z. Dvir and A. Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, SIAM J. on Computing, 36(5) (2006), 1404\u20131434.","journal-title":"SIAM J. on Computing"},{"key":"2537_CR9","doi-asserted-by":"crossref","unstructured":"A. Gabizon and R. Raz: Deterministic extractors for affine sources over large fields. In 46th Annual FOCS, pages 407\u2013418, 2005.","DOI":"10.1109\/SFCS.2005.31"},{"key":"2537_CR10","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and M. Karpinski: The matching problem for bipartite graphs with polynomially bounded permanents is in NC (extended abstract), In Proceedings of the 28th Annual FOCS, pages 166\u2013172, 1987.","DOI":"10.1109\/SFCS.1987.56"},{"issue":"6","key":"2537_CR11","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Grigoriev","year":"1990","unstructured":"D. Grigoriev, M. Karpinski, and M. F. Singer: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. on Computing, 19(6) (1990), 1059\u20131063.","journal-title":"SIAM J. on Computing"},{"issue":"1\u20132","key":"2537_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"V. Kabanets and R. Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, 13(1\u20132) (2004), 1\u201346.","journal-title":"Computational Complexity"},{"key":"2537_CR13","doi-asserted-by":"crossref","unstructured":"Z. S. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich: Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. To appear in STOC, 2010.","DOI":"10.1145\/1806689.1806779"},{"issue":"2","key":"2537_CR14","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0304-3975(95)00162-X","volume":"157","author":"M. Karpinski","year":"1996","unstructured":"M. Karpinski and I. Shparlinski: On some approximation problems concerning sparse polynomials over finite fields, Theoretical Computer Science, 157(2) (1996), 259\u2013266.","journal-title":"Theoretical Computer Science"},{"key":"2537_CR15","doi-asserted-by":"crossref","unstructured":"N. Kayal and S. Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual FOCS, pages 198\u2013207, 2009.","DOI":"10.1109\/FOCS.2009.67"},{"key":"2537_CR16","doi-asserted-by":"crossref","unstructured":"N. Kayal and N. Saxena: Polynomial identity testing for depth 3 circuits. In Proceedingds of the 21st Annual IEEE Conference on Computational Complexity, pages 9\u201317, 2006.","DOI":"10.1109\/CCC.2006.34"},{"key":"2537_CR17","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. Spielman: Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual STOC, pages 216\u2013223, 2001.","DOI":"10.1145\/380752.380801"},{"key":"2537_CR18","doi-asserted-by":"crossref","unstructured":"D. Lewin and S. Vadhan: Checking polynomial identities over any field: Towards a derandomization? In Proceedings of the 30th Annual STOC, pages 428\u2013437, 1998.","DOI":"10.1145\/276698.276856"},{"key":"2537_CR19","unstructured":"L. Lovsz: On determinants, matchings, and random algorithms. In L. Budach, editor, Fundamentals of Computing Theory, Akademia-Verlag, 1979."},{"issue":"1","key":"2537_CR20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. Vazirani, and V. Vazirani: Matching is as easy as matrix inversion. Combinatorica, 7(1) (1987), 105\u2013113.","journal-title":"Combinatorica"},{"issue":"1","key":"2537_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"R. Raz and A. Shpilka: Deterministic polynomial identity testing in non commutative models. Computational Complexity, 14(1) (2005), 1\u201319.","journal-title":"Computational Complexity"},{"key":"2537_CR22","doi-asserted-by":"crossref","unstructured":"N. Saxena and C. Seshadhri: An almost optimal rank bound for depth-3 identities. In Proceedings of the 24th annual CCC, pages 137\u2013148, 2009.","DOI":"10.1109\/CCC.2009.20"},{"issue":"2","key":"2537_CR23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jcss.1996.0017","volume":"52","author":"R. E. Schapire","year":"1996","unstructured":"R. E. Schapire and L. M. Sellie: Learning sparse multivariate polynomials over a field with queries and counterexamples. J. of Computer and System Sciences, 52(2) (1996), 201\u2013213.","journal-title":"J. of Computer and System Sciences"},{"issue":"4","key":"2537_CR24","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. JACM, 27(4) (1980), 701\u2013717.","journal-title":"JACM"},{"issue":"6","key":"2537_CR25","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"A. Shpilka","year":"2009","unstructured":"A. Shpilka: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. on Computing, 38(6) (2009), 2130\u20132161.","journal-title":"SIAM J. on Computing"},{"key":"2537_CR26","doi-asserted-by":"crossref","unstructured":"A. Shpilka and I. Volkovich: Read-once polynomial identity testing. In Proceedings of the 40th Annual STOC, pages 507\u2013516, 2008.","DOI":"10.1145\/1374376.1374448"},{"key":"2537_CR27","doi-asserted-by":"crossref","unstructured":"A. Shpilka and I. Volkovich: Improved polynomial identity testing for read-once formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop RANDOM, LNCS, pages 700\u2013713, 2009.","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"2537_CR28","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01438278","volume":"5","author":"K. Werther","year":"1994","unstructured":"K. Werther: The complexity of sparse polynomial interpolation over finite fields. Applicable Algebra in Engineering, Communication and Computing, 5 (1994), 91\u2013103.","journal-title":"Applicable Algebra in Engineering, Communication and Computing"},{"key":"2537_CR29","doi-asserted-by":"crossref","unstructured":"R. Zippel: Probabilistic algorithms for sparse polynomials. In Symbolic and algebraic computation, pages 216\u2013226. 1979.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2537-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-011-2537-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2537-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,9]],"date-time":"2025-03-09T22:22:27Z","timestamp":1741558947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-011-2537-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["2537"],"URL":"https:\/\/doi.org\/10.1007\/s00493-011-2537-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}