{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T05:48:14Z","timestamp":1772689694085,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:00:00Z","timestamp":1559001600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:00:00Z","timestamp":1559001600000},"content-version":"vor","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":[[2019,12]]},"DOI":"10.1007\/s00037-019-00185-4","type":"journal-article","created":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T07:25:43Z","timestamp":1559028343000},"page":"545-572","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach"],"prefix":"10.1007","volume":"28","author":[{"given":"Suryajith","family":"Chillara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,28]]},"reference":[{"key":"185_CR1","unstructured":"Manindra Agrawal & V\u00a0Vinay (2008). Arithmetic circuits: A chasm at depth four. In Proceedings of Foundations of Computer Science (FOCS), 67\u201375. IEEE"},{"issue":"1","key":"185_CR2","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0890-5401(90)90036-H","volume":"84","author":"Jin-Yi Cai","year":"1990","unstructured":"Cai, Jin-Yi: A note on the determinant and permanent problem. Information and Computation 84(1), 119\u2013127 (1990)","journal-title":"Information and Computation"},{"key":"185_CR3","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Xi\u00a0Chen & Dong Li (2008). A quadratic lower bound for the permanent and determinant problem over any characteristic$$\\ne $$ 2. In Proceedings of Symposium on Theory of Computing, 491\u2013498. ACM","DOI":"10.1145\/1374376.1374446"},{"key":"185_CR4","unstructured":"Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi & V.\u00a0Vinay (2016). The Chasm at Depth Four, and Tensor Rank: Old results, new insights. Electronic Colloquium on Computational Complexity (ECCC) 23, 96. http:\/\/eccc.hpi-web.de\/report\/2016\/096"},{"key":"185_CR5","doi-asserted-by":"crossref","unstructured":"David Cox, John Little & Donal O'shea (2007). Ideals, varieties, and algorithms, volume\u00a03. Springer","DOI":"10.1007\/978-0-387-35651-8"},{"key":"185_CR6","doi-asserted-by":"crossref","unstructured":"Herv\u00e9 Fournier, Nutan Limaye, Guillaume Malod & Srikanth Srinivasan (2014). Lower bounds for depth 4 formulas computing iterated matrix multiplication. In Proceedings of Symposium on Theory of Computing, 128\u2013135. ACM. http:\/\/doi.acm.org\/10.1145\/2591796.2591824","DOI":"10.1145\/2591796.2591824"},{"key":"185_CR7","doi-asserted-by":"crossref","unstructured":"Joachim von\u00a0zur Gathen (1986). Permanent and Determinant. In Proceedings of Foundations of Computer Science (FOCS), 398\u2013401. IEEE Computer Society","DOI":"10.1109\/SFCS.1986.42"},{"key":"185_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0024-3795(87)90337-5","volume":"96","author":"Joachim von zur Gathen","year":"1987","unstructured":"Joachim von zur Gathen: Permanent and determinant. Linear Algebra and its Applications 96, 87\u2013100 (1987)","journal-title":"Linear Algebra and its Applications"},{"key":"185_CR9","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2013). Approaching the chasm at depth four. In Proceedings of the Conference on Computational Complexity (CCC)","DOI":"10.1109\/CCC.2013.16"},{"issue":"2","key":"185_CR10","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00224-010-9308-1","volume":"49","author":"Maurice Jansen","year":"2011","unstructured":"Jansen, Maurice: Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials. Theory of Computing Systems 49(2), 343\u2013354 (2011)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"185_CR11","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0214050","volume":"14","author":"Kyriakos Kalorkoti","year":"1985","unstructured":"Kalorkoti, Kyriakos: A Lower Bound for the Formula Size of Rational Functions. SIAM Journal of Computing 14(3), 678\u2013687 (1985)","journal-title":"SIAM Journal of Computing"},{"key":"185_CR12","unstructured":"Neeraj Kayal (2012). An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC) 19, 81. http:\/\/eccc.hpi-web.de\/report\/2012\/081"},{"key":"185_CR13","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal, Nutan Limaye, Chandan Saha & Srikanth Srinivasan (2014a). An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Circuits. In Proceedings of Foundations of Computer Science (FOCS). IEEE","DOI":"10.1109\/FOCS.2014.15"},{"key":"185_CR14","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal, Chandan Saha & Ramprasad Saptharishi (2014b). A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of Symposium on Theory of Computing, 146\u2013153. ACM. http:\/\/doi.acm.org\/10.1145\/2591796.2591847","DOI":"10.1145\/2591796.2591847"},{"key":"185_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"Pascal Koiran","year":"2012","unstructured":"Koiran, Pascal: Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci. 448, 56\u201365 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"185_CR16","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar & Shubhangi Saraf (2014a). The limits of depth reduction for arithmetic formulas: it's all about the top fan-in. In Proceedings of Symposium on Theory of Computing, 136\u2013145. ACM. http:\/\/doi.acm.org\/10.1145\/2591796.2591827","DOI":"10.1145\/2591796.2591827"},{"key":"185_CR17","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar & Shubhangi Saraf (2014b). On the power of homogeneous depth $$4$$ arithmetic circuits. In Proceedings of Foundations of Computer Science (FOCS). IEEE","DOI":"10.1109\/FOCS.2014.46"},{"key":"185_CR18","unstructured":"Mrinal Kumar & Shubhangi Saraf (2016a). Arithmetic circuits with locally low algebraic rank. In Proceedings of Conference on Computational Complexity (CCC)"},{"key":"185_CR19","unstructured":"Mrinal Kumar & Shubhangi Saraf (2016b). Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In Proceedings of Conference on Computational Complexity (CCC)"},{"key":"185_CR20","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0024-3795(89)90465-5","volume":"114","author":"Roy Meshulam","year":"1989","unstructured":"Meshulam, Roy: On two extremal matrix problems. Linear Algebra and its Applications 114, 261\u2013271 (1989)","journal-title":"Linear Algebra and its Applications"},{"issue":"79","key":"185_CR21","doi-asserted-by":"publisher","first-page":"4241","DOI":"10.1155\/S1073792804142566","volume":"2004","author":"Thierry Mignon & Nicolas Ressayre","year":"2004","unstructured":"Thierry Mignon & Nicolas Ressayre: A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices 2004(79), 4241\u20134253 (2004)","journal-title":"International Mathematics Research Notices"},{"issue":"2","key":"185_CR22","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan & Avi Wigderson","year":"1994","unstructured":"Noam Nisan & Avi Wigderson: Hardness vs Randomness. J. Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"185_CR23","unstructured":"Ramprasad Saptharishi (2015). A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/ . Github survey"},{"key":"185_CR24","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\u00e9bastien Tavenas","year":"2013","unstructured":"S\u00e9bastien Tavenas (2013). Improved Bounds for Reduction to Depth 4 and Depth 3. In Proceedings of Mathematical Foundations of Computer Science (MFCS), 813\u2013824"},{"issue":"1","key":"185_CR25","first-page":"116","volume":"75","author":"Seinosuke Toda","year":"1992","unstructured":"Toda, Seinosuke: Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems 75(1), 116\u2013124 (1992)","journal-title":"IEICE Transactions on Information and Systems"},{"key":"185_CR26","unstructured":"Leslie\u00a0G Valiant (1979). Completeness classes in algebra. In Proceedings of Symposium on Theory of Computing (STOC), 249\u2013261. ACM"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00185-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-019-00185-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00185-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,18]],"date-time":"2022-09-18T18:45:47Z","timestamp":1663526747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-019-00185-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,28]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["185"],"URL":"https:\/\/doi.org\/10.1007\/s00037-019-00185-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,28]]},"assertion":[{"value":"3 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}