{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:51Z","timestamp":1740109491762,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,4,11]],"date-time":"2016-04-11T00:00:00Z","timestamp":1460332800000},"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":[[2016,6]]},"DOI":"10.1007\/s00037-016-0131-1","type":"journal-article","created":{"date-parts":[[2016,4,14]],"date-time":"2016-04-14T04:52:19Z","timestamp":1460609539000},"page":"455-505","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas"],"prefix":"10.1007","volume":"25","author":[{"given":"Rafael","family":"Oliveira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben lee","family":"Volk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,11]]},"reference":[{"key":"131_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":"131_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal, R. Gurjar, A. Korwar & N. Saxena (2015). Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44(3), 669\u2013697. URL http:\/\/dx.doi.org\/10.1137\/140975103 .","DOI":"10.1137\/140975103"},{"issue":"2","key":"131_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":"131_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 STOC, 599\u2013614.","DOI":"10.1145\/2213977.2214033"},{"key":"131_CR5","unstructured":"M. Agrawal, C. Saha & N. Saxena (2013). Quasi-polynomial hitting-set for set-depth- $${\\Delta}$$ \u0394 formulas. In Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, 321\u2013330."},{"key":"131_CR6","doi-asserted-by":"crossref","unstructured":"M. Agrawal & V. Vinay (2008). Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual FOCS, 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"131_CR7","doi-asserted-by":"crossref","unstructured":"N. Alon & J. Spencer (2008). The probabilistic method. J. Wiley, 3rd edition.","DOI":"10.1002\/9780470277331"},{"key":"131_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 CCC, 273\u2013282.","DOI":"10.1109\/CCC.2011.18"},{"issue":"4","key":"131_CR9","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R. A. DeMillo","year":"1978","unstructured":"DeMillo R. A., Lipton R. J. (1978) A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4): 193\u2013195","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"131_CR10","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z. Dvir","year":"2006","unstructured":"Dvir Z., Shpilka A. (2006) Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. on Computing 36(5): 1404\u20131434","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"131_CR11","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 J. on Computing 39(4): 1279\u20131293","journal-title":"SIAM J. on Computing"},{"key":"131_CR12","doi-asserted-by":"crossref","unstructured":"M. A. Forbes, R. Saptharishi & A. Shpilka (2014). Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, 867\u2013875.","DOI":"10.1145\/2591796.2591816"},{"key":"131_CR13","doi-asserted-by":"crossref","unstructured":"M. A. Forbes & A. Shpilka (2012). On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the 44th annual STOC, 163\u2013172.","DOI":"10.1145\/2213977.2213995"},{"key":"131_CR14","unstructured":"M. A. Forbes & A. Shpilka (2013). Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, 243\u2013252. URL http:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS.2013.34 ."},{"key":"131_CR15","unstructured":"A. Gupta (2014). Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. Electronic Colloquium on Computational Complexity (ECCC) 21, 130. URL http:\/\/eccc.hpi-web.de\/report\/2014\/130 ."},{"key":"131_CR16","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal & R. Saptharishi (2013). Arithmetic Circuits: A Chasm at Depth Three. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 578\u2013587.","DOI":"10.1109\/FOCS.2013.68"},{"key":"131_CR17","unstructured":"R. Gurjar, A. Korwar, N. Saxena & T. Thierauf (2015). Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, D. Zuckerman, editor, volume 33 of LIPIcs, 323\u2013346. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.CCC.2015.323 ."},{"key":"131_CR18","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 STOC, 262\u2013272.","DOI":"10.1145\/800141.804674"},{"key":"131_CR19","doi-asserted-by":"crossref","unstructured":"V. Kabanets & R. Impagliazzo (2003). Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the 35th Annual STOC, 355\u2013364.","DOI":"10.1145\/780542.780595"},{"issue":"1-2","key":"131_CR20","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-2): 1\u201346","journal-title":"Computational Complexity"},{"key":"131_CR21","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. Comput. 42(6), 2114\u20132131. URL http:\/\/dx.doi.org\/10.1137\/110824516 .","DOI":"10.1137\/110824516"},{"issue":"3","key":"131_CR22","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s00493-011-2537-3","volume":"31","author":"Z. S. Karnin","year":"2011","unstructured":"Karnin Z. S., Shpilka A. (2011) Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31(3): 333\u2013364","journal-title":"Combinatorica"},{"key":"131_CR23","doi-asserted-by":"crossref","unstructured":"N. Kayal, C. Saha & R. Saptharishi (2014). A super-polynomial lower bound for regular arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, 146\u2013153.","DOI":"10.1145\/2591796.2591847"},{"key":"131_CR24","doi-asserted-by":"crossref","unstructured":"N. Kayal & S. Saraf (2009). Blackbox Polynomial Identity Testing for Depth 3 Circuits. In Proceedings of the 50th Annual FOCS, 198\u2013207.","DOI":"10.1109\/FOCS.2009.67"},{"issue":"2","key":"131_CR25","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","volume":"16","author":"N. Kayal","year":"2007","unstructured":"Kayal N., Saxena N. (2007) Polynomial Identity Testing for Depth 3 Circuits. Computational Complexity 16(2): 115\u2013138","journal-title":"Computational Complexity"},{"key":"131_CR26","unstructured":"P. Koiran (2010). Arithmetic circuits: the chasm at depth four gets wider. CoRR arXiv:1006.4700 [abs]."},{"key":"131_CR27","doi-asserted-by":"crossref","unstructured":"N. Nisan (1991). Lower Bounds for Non-Commutative Computation. In Proceedings of the 23rd Annual STOC, 410\u2013418.","DOI":"10.1145\/103418.103462"},{"key":"131_CR28","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":"131_CR29","unstructured":"R. Oliveira, A. Shpilka & B. L. Volk (2015). Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, D. Zuckerman, editor, volume 33 of LIPIcs, 304\u2013322. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.CCC.2015.304 ."},{"issue":"1","key":"131_CR30","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":"131_CR31","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"},{"issue":"1","key":"131_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz R., Shpilka A. (2005) Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1): 1\u201319","journal-title":"Computational Complexity"},{"issue":"4","key":"131_CR33","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. (2008) A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. on Computing 38(4): 1624\u20131647","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"131_CR34","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":"131_CR35","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 STOC, 421\u2013430.","DOI":"10.1145\/1993636.1993693"},{"key":"131_CR36","doi-asserted-by":"crossref","unstructured":"N. Saxena & C. Seshadhri (2011). Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn\u2019t matter. In Proceedings of the 43rd Annual STOC, 431\u2013440.","DOI":"10.1145\/1993636.1993694"},{"issue":"4","key":"131_CR37","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"Schwartz J. T. (1980) Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4): 701\u2013717","journal-title":"J. ACM"},{"key":"131_CR38","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2008). Read-once Polynomial Identity Testing. In Proceedings of the 40th Annual STOC, 507\u2013516.","DOI":"10.1145\/1374376.1374448"},{"key":"131_CR39","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2009). Improved Polynomial Identity Testing for Read-Once Formulas. In APPROX-RANDOM, 700\u2013713.","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"131_CR40","doi-asserted-by":"crossref","unstructured":"A. Shpilka & I. Volkovich (2010). On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. In ICALP (1), 408\u2013419.","DOI":"10.1007\/978-3-642-14165-2_35"},{"issue":"3-4","key":"131_CR41","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A. Shpilka","year":"2010","unstructured":"Shpilka A., Yehudayoff A. (2010) Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3-4): 207\u2013388","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"131_CR42","doi-asserted-by":"crossref","unstructured":"S. Tavenas (2013). Improved Bounds for Reduction to Depth 4 and Depth 3. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, 813\u2013824.","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"131_CR43","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, S. Skyum, S. Berkowitz & C. Rackoff (1983). Fast parallel computation of polynomials using few processors. SIAM J. on Computing 12(4), 641\u2013644. ISSN 0097-5397 (print), 1095-7111 (electronic).","DOI":"10.1137\/0212043"},{"key":"131_CR44","doi-asserted-by":"crossref","unstructured":"R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In EUROSAM, 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-016-0131-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0131-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0131-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0131-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,11]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["131"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0131-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2016,4,11]]}}}