{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:33Z","timestamp":1725795873147},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_62","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"751-762","source":"Crossref","is-referenced-by-count":4,"title":["Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits"],"prefix":"10.1007","author":[{"given":"Mrinal","family":"Kumar","sequence":"first","affiliation":[]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: A chasm at depth four. In: Proceedings of the 49th Annual FOCS, pp. 67\u201375 (2008)","key":"62_CR1","DOI":"10.1109\/FOCS.2008.32"},{"unstructured":"Chillara, S., Mukhopadhyay, P.: Depth-4 lower bounds, determinantal complexity: A unified approach. CoRR, abs\/1308.1640v3 (2013)","key":"62_CR2"},{"unstructured":"Fournier, H., Limaye, N., Malod, G., Srinivasan, S.: Lower bounds for depth 4 formulas computing iterated matrix multiplication. In: STOC 2014 (to appear, 2014)","key":"62_CR3"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. In: Proceedings of CCC (2013)","key":"62_CR4","DOI":"10.1109\/CCC.2013.16"},{"key":"62_CR5","first-page":"81","volume":"19","author":"N. Kayal","year":"2012","unstructured":"Kayal, N.: An exponential lower bound for the sum of powers of bounded degree polynomials. ECCC\u00a019, 81 (2012)","journal-title":"ECCC"},{"doi-asserted-by":"crossref","unstructured":"Kayal, N., Limaye, N., Saha, C., Srinivasan, S.: An exponential lower bound for homogeneous depth four arithmetic formulas. ECCC (2014)","key":"62_CR6","DOI":"10.1109\/FOCS.2014.15"},{"key":"62_CR7","first-page":"91","volume":"20","author":"N. Kayal","year":"2013","unstructured":"Kayal, N., Saha, C., Saptharishi, R.: A super-polynomial lower bound for regular arithmetic formulas. ECCC\u00a020, 91 (2013)","journal-title":"ECCC"},{"key":"62_CR8","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P. Koiran","year":"2012","unstructured":"Koiran, P.: Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science\u00a0448, 56\u201365 (2012)","journal-title":"Theoretical Computer Science"},{"unstructured":"Kumar, M., Saraf, S.: The limits of depth reduction for arithmetic formulas: It\u2019s all about the top fan-in. In: STOC 2014 (to appear, 2014)","key":"62_CR9"},{"doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. ECCC (2013)","key":"62_CR10","DOI":"10.1007\/978-3-662-43948-7_62"},{"doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: On the power of homogeneous depth 4 arithmetic circuits. ECCC (2014)","key":"62_CR11","DOI":"10.1109\/FOCS.2014.46"},{"unstructured":"Limaye, N., Saha, C., Srinivasan, S.: Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In: STOC 2014 (to appear, 2014)","key":"62_CR12"},{"doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. In: Proceedings of the 36th Annual FOCS, pp. 16\u201325 (1995)","key":"62_CR13","DOI":"10.7146\/brics.v2i43.19944"},{"doi-asserted-by":"crossref","unstructured":"Raz, R., Yehudayoff, A.: Lower bounds and separations for constant depth multilinear circuits. In: Conference on Computational Complexity, pp. 128\u2013139 (June 2008)","key":"62_CR14","DOI":"10.1109\/CCC.2008.8"},{"issue":"1","key":"62_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4086\/toc.2010.v006a007","volume":"6","author":"R. Raz","year":"2010","unstructured":"Raz, R.: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing\u00a06(1), 135\u2013177 (2010)","journal-title":"Theory of Computing"},{"key":"62_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/978-3-642-40313-2_71","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S. Tavenas","year":"2013","unstructured":"Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 813\u2013824. Springer, Heidelberg (2013)"},{"key":"62_CR17","first-page":"249","volume-title":"Proceedings of the 11th Annual STOC, STOC 1979","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: Completeness classes in algebra. In: Proceedings of the 11th Annual STOC, STOC 1979, pp. 249\u2013261. ACM, New York (1979)"},{"issue":"4","key":"62_CR18","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM Journal of Computation\u00a012(4), 641\u2013644 (1983)","journal-title":"SIAM Journal of Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:30:38Z","timestamp":1558909838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}