{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T14:06:31Z","timestamp":1725113191693},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T00:00:00Z","timestamp":1663545600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T00:00:00Z","timestamp":1663545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00037-022-00228-3","type":"journal-article","created":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T06:02:47Z","timestamp":1663567367000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Lower Bound on Determinantal Complexity"],"prefix":"10.1007","volume":"31","author":[{"given":"Mrinal","family":"Kumar","sequence":"first","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":[[2022,9,19]]},"reference":[{"key":"228_CR1","doi-asserted-by":"crossref","unstructured":"Boris Alexeev, Michael A. Forbes & Jacob Tsimerman (2011).Tensor Rank: Some Lower and Upper Bounds. In 26th Annual IEEE Conference on Computational Complexity (CCC2011), 283\u2013291. IEEE Computer Society. https:\/\/doi.org\/10.1109\/CCC.2011.28.","DOI":"10.1109\/CCC.2011.28"},{"key":"228_CR2","doi-asserted-by":"crossref","unstructured":"Jarod Alper, Tristram Bogart & Mauricio Velasco (2017).A Lower Bound for the Determinantal Complexity of a Hypersurface.Found. Comput. Math. 17(3), 829\u2013836. https:\/\/doi.org\/10.1007\/s10208-015-9300-x.","DOI":"10.1007\/s10208-015-9300-x"},{"key":"228_CR3","doi-asserted-by":"crossref","unstructured":"Markus Bl\u00c4ser (1999).$$A \\frac{5}{2} n^2$$ -Lower Bound for the Rank of n \u00d7 n Matrix Multiplication over Arbitrary Fields. In 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), 45\u201350. IEEE Computer Society. https:\/\/doi.org\/10.1109\/SFFCS.1999.814576.","DOI":"10.1109\/SFFCS.1999.814576"},{"key":"228_CR4","doi-asserted-by":"crossref","unstructured":"Mark R. Brown & David P. Dobkin (1980). An Improved Lower Bound on Polynomial Multiplication. IEEE Trans. Computers 29(5),337\u2013340. https:\/\/doi.org\/10.1109\/TC.1980.1675583.","DOI":"10.1109\/TC.1980.1675583"},{"key":"228_CR5","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai (1990). A Note on the Determinant and Permanent Problem. Inf. Comput. 84(1), 119\u2013127. https:\/\/doi.org\/10.1016\/0890-5401(90)90036-H..","DOI":"10.1016\/0890-5401(90)90036-H"},{"key":"228_CR6","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Xi Chen & Dong Li (2010). Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. Comput. Complex.19(1), 37\u201356. https:\/\/doi.org\/10.1007\/s00037-009-0284-2.","DOI":"10.1007\/s00037-009-0284-2"},{"key":"228_CR7","doi-asserted-by":"crossref","unstructured":"Prerona Chatterjee, Mrinal Kumar, Adrian She & Ben Lee Volk (2022). Quadratic Lower Bounds for Algebraic Branching Programs and Formulas. Comput. Complex. 31(2), 8. https:\/\/doi.org\/10.1007\/s00037-022-00223-8.","DOI":"10.1007\/s00037-022-00223-8"},{"key":"228_CR8","doi-asserted-by":"crossref","unstructured":"Xi Chen, Neeraj Kayal & Avi Wigderson (2011). Partial Derivatives in Arithmetic Complexity. Foundations and Trends in Theoretical Computer Science https:\/\/doi.org\/10.1561\/0400000043.","DOI":"10.1561\/0400000043"},{"key":"228_CR9","doi-asserted-by":"crossref","unstructured":"David A. Cox, John B. Little & Donal O\u2019Shea (2007). Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer. https:\/\/doi.org\/10.1007\/978-0-387-35651-8.","DOI":"10.1007\/978-0-387-35651-8"},{"key":"228_CR10","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen (1987). Permanent and determinant. Linear Algebra and its Applications 96, 87\u2013100. https:\/\/core.ac.uk\/download\/pdf\/82095887.pdf\".","DOI":"10.1016\/0024-3795(87)90337-5"},{"key":"228_CR11","unstructured":"Joe Harris (1995). Algebraic geometry, volume 133 of Graduate Texts in Mathematics. Springer-Verlag, New York.ISBN 0-387-97716-3,xx+328 . https:\/\/doi.org\/10.1007\/978-1-4757-2189-8.A first course, Corrected reprint of the 1992 original."},{"key":"228_CR12","doi-asserted-by":"crossref","unstructured":"Christian Ikenmeyer & J.M. Landsberg (2017). On the complexity of the permanent in various computational models.Journal of Pure and Applied Algebra 221(12), 2911\u20132927. ISSN 00224049 https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022404917300336.","DOI":"10.1016\/j.jpaa.2017.02.008"},{"key":"228_CR13","doi-asserted-by":"crossref","unstructured":"Kyriakos Kalorkoti (1985). A Lower Bound for the Formula Size of Rational Functions. SIAM Journal of Computing 14(3), 678\u2013687. https:\/\/doi.org\/10.1137\/0214050..","DOI":"10.1137\/0214050"},{"key":"228_CR14","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar (2019). A quadratic lower bound for homogeneous algebraic branching programs. Computational Complexity 28(3), 409435. https:\/\/doi.org\/10.1007\/s00037-019-00186-3.","DOI":"10.1007\/s00037-019-00186-3"},{"key":"228_CR15","doi-asserted-by":"crossref","unstructured":"J.M. Landsberg & Nicolas Ressayre (2017). Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards Valiant\u2019s conjecture. Differential Geometry and its Applications 55, 146\u2013166. ISSN 0926-2245. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S092622451730044X.","DOI":"10.1016\/j.difgeo.2017.03.017"},{"key":"228_CR16","doi-asserted-by":"crossref","unstructured":"Joseph M. Landsberg, Laurent Manivel & Nicolas Ressayre (2013). Hypersurfaces with degenerate duals and the geometric complexity theory program. Comment. Math. Helv. 88(2), 469\u2013484. ISSN 0010-2571. https:\/\/doi.org\/10.4171\/CMH\/292.","DOI":"10.4171\/CMH\/292"},{"key":"228_CR17","doi-asserted-by":"crossref","unstructured":"Marvin Marcus & Henryk Minc (1961). On the relation between the determinant and the permanent. Illinois J. Math. 5(3), 376\u2013381. https:\/\/doi.org\/10.1215\/ijm\/1255630882..","DOI":"10.1215\/ijm\/1255630882"},{"key":"228_CR18","doi-asserted-by":"crossref","unstructured":"Roy Meshulam (1989). On two extremal matrix problems. Linear Algebra and its Applications 114\u2013115, 261\u2013271. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379589904655.","DOI":"10.1016\/0024-3795(89)90465-5"},{"key":"#cr-split#-228_CR19.1","doi-asserted-by":"crossref","unstructured":"Thierry Mignon & Nicolas Ressayre (2004). A quadratic bound for the determinant and permanent problem. International","DOI":"10.1155\/S1073792804142566"},{"key":"#cr-split#-228_CR19.2","doi-asserted-by":"crossref","unstructured":"Mathematics Research Notes 2004(79), 4241-4253. Available on citeseer:10.1.1.106.4910.","DOI":"10.1155\/S1073792804142566"},{"key":"228_CR20","unstructured":"George P\u00d3lya (1913). Aufgabe 424. Archiv der Mathematik und Physik 20, 271. http:\/\/babel.hathitrust.org\/cgi\/pt?id=mdp.39015085215716;seq=399."},{"key":"228_CR21","unstructured":"Ramprasad Saptharishi (2015). A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/. Github survey."},{"key":"228_CR22","doi-asserted-by":"crossref","unstructured":"Amir Shpilka (2003). Lower Bounds for Matrix Product. SIAM J. Comput. 32(5), 1185\u20131200. https:\/\/doi.org\/10.1137\/S0097539702405954.","DOI":"10.1137\/S0097539702405954"},{"key":"228_CR23","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207\u2013388. ISSN 1551-305X. https:\/\/doi.org\/10.1561\/0400000039.","DOI":"10.1561\/0400000039"},{"key":"228_CR24","unstructured":"G\u00e1bor Szeg\u0150 (1913). L\u00f6sung zu Aufgabe 424. Archiv der Mathematik und Physik 21, 291\u2013292. http:\/\/hdl.handle.net\/2027\/uc1.b2958231."},{"key":"228_CR25","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing (STOC 1979), 249\u2013261. ACM. https:\/\/doi.org\/10.1145\/800135.804419.","DOI":"10.1145\/800135.804419"},{"key":"228_CR26","unstructured":"Akihiro Yabe (2015). Bi-polynomial rank and determinantal complexity. CoRR. http:\/\/arxiv.org\/abs\/1504.00151."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00228-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00228-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00228-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:27:50Z","timestamp":1669303670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00228-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,19]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["228"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00228-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,19]]},"assertion":[{"value":"31 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}