{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T03:07:59Z","timestamp":1774321679135,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00037-024-00258-z","type":"journal-article","created":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T13:02:38Z","timestamp":1725109358000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Determinants vs. Algebraic Branching Programs"],"prefix":"10.1007","volume":"33","author":[{"given":"Abhranil","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mrinal","family":"Kumar","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":[[2024,8,31]]},"reference":[{"key":"258_CR1","doi-asserted-by":"crossref","unstructured":"Jarod Alper, Tristram Bogart & Mauricio Velasco (2017).\nA Lower Bound for the Determinantal Complexity of a Hypersurface.\nFound. Comput. Math. 17(3), 829\u2013836. URL https:\/\/doi.org\/10.1007\/s10208-015-9300-x.","DOI":"10.1007\/s10208-015-9300-x"},{"key":"258_CR2","doi-asserted-by":"crossref","unstructured":"Walter Baur & Volker Strassen (1983). The Complexity of Partial\nDerivatives. Theoretical Computer Science 22, 317\u2013330.","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"258_CR3","doi-asserted-by":"crossref","unstructured":"Stuart J. Berkowitz (1984). On computing the determinant in small\nparallel time using a small number of processors. Information Processing\nLetters 18(3), 147 \u2013 150. ISSN 0020-0190.","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"258_CR4","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Xi Chen & Dong Li (2010). Quadratic Lower Bound for\nPermanent Vs. Determinant in any Characteristic. Comput. Complex.\n19(1), 37\u201356. URL https:\/\/doi.org\/10.1007\/s00037-009-0284-2.","DOI":"10.1007\/s00037-009-0284-2"},{"key":"258_CR5","doi-asserted-by":"crossref","unstructured":"Prerona Chatterjee, Mrinal Kumar, Adrian She & Ben Lee\nVolk (2022). Quadratic Lower Bounds for Algebraic Branching Programs\nand Formulas. Comput. Complex. 31(2), 8. URL https:\/\/doi.org\/10.1007\/s00037-022-00223-8.","DOI":"10.1007\/s00037-022-00223-8"},{"key":"258_CR6","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen (1987). Permanent and determinant. Linear\nAlgebra and its Applications 96, 87\u2013100. URL https:\/\/core.ac.uk\/download\/pdf\/82095887.pdf.","DOI":"10.1016\/0024-3795(87)90337-5"},{"key":"258_CR7","unstructured":"Joe Harris (1995). Algebraic geometry, volume 133 of Graduate Texts\nin Mathematics. Springer-Verlag, New York. ISBN 0-387-97716-3,\nxx+328 . A first course, Corrected reprint of the 1992 original."},{"key":"258_CR8","doi-asserted-by":"crossref","unstructured":"Kyriakos Kalorkoti (1985). A Lower Bound for the Formula Size\nof Rational Functions. SIAM Journal of Computing 14(3), 678\u2013687.","DOI":"10.1137\/0214050"},{"key":"258_CR9","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer & Avi Wigderson (1993). On Span Programs.\nIn Proceedings of the 8th Annual Structure in Complexity Theory\nConference (Structures 1993), 102\u2013111. IEEE Computer Society. URL https:\/\/doi.org\/10.1109\/SCT.1993.336536.","DOI":"10.1109\/SCT.1993.336536"},{"key":"258_CR10","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar (2019). A quadratic lower bound for homogeneous\nalgebraic branching programs. Computational Complexity 28(3), 409\u2013\n435. URL https:\/\/doi.org\/10.1007\/s00037-019-00186-3.","DOI":"10.1007\/s00037-019-00186-3"},{"key":"258_CR11","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar & Ben Lee Volk (2022). A Lower Bound on Determinantal\nComplexity. Comput. Complex. 31(2), 12. URL https:\/\/doi.org\/10.1007\/s00037-022-00228-3.","DOI":"10.1007\/s00037-022-00228-3"},{"key":"258_CR12","doi-asserted-by":"crossref","unstructured":"J.M. Landsberg & Nicolas Ressayre (2017). Permanent v. determinant:\nAn exponential lower bound assuming symmetry and a potential\npath towards Valiant\u2019s conjecture. Differential Geometry and\nits Applications 55, 146\u2013166. ISSN 0926-2245. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S092622451730044X.","DOI":"10.1016\/j.difgeo.2017.03.017"},{"key":"258_CR13","doi-asserted-by":"crossref","unstructured":"Satyanarayana V. Lokam (2009). Complexity Lower Bounds using\nLinear Algebra. Found. Trends Theor. Comput. Sci. 4(1-2), 1\u2013155. URL https:\/\/doi.org\/10.1561\/0400000011.","DOI":"10.1561\/0400000011"},{"key":"258_CR14","unstructured":"Meena Mahajan & V. Vinay (1997). A Combinatorial Algorithm\nfor the Determinant. In Proceedings of the 8th Annual ACMSIAM\nSymposium on Discrete Algorithms (SODA 1997), 730\u2013738.\nURL https:\/\/dl.acm.org\/doi\/10.5555\/314161.314429. Available\non citeseer:10.1.1.31.1673."},{"key":"258_CR15","doi-asserted-by":"crossref","unstructured":"Thierry Mignon & Nicolas Ressayre (2004). A quadratic\nbound for the determinant and permanent problem. International\nMathematics Research Notes 2004(79), 4241\u20134253. Available on\nciteseer:10.1.1.106.4910.","DOI":"10.1155\/S1073792804142566"},{"key":"258_CR16","unstructured":"Eduard Ivanovich Nechiporuk (1966). On a Boolean function.\nDokl. Akad. Nauk SSSR 169, 765\u2013766. URL http:\/\/mi.mathnet.ru\/dan32449."},{"key":"258_CR17","unstructured":"Ran Raz (2010). Elusive Functions and Lower Bounds for Arithmetic\nCircuits. Theory of Computing 6(7), 135\u2013177. URL https:\/\/theoryofcomputing.org\/articles\/v006a007."},{"key":"258_CR18","unstructured":"Ramprasad Saptharishi (2015). A survey of lower bounds in\narithmetic circuit complexity. URL https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/. Github survey."},{"key":"258_CR19","doi-asserted-by":"crossref","unstructured":"Victor Shoup & Roman Smolensky (1997). Lower Bounds for Polynomial\nEvaluation and Interpolation Problems. Comput. Complex. 6(4),\n301\u2013311. URL https:\/\/doi.org\/10.1007\/BF01270384.","DOI":"10.1007\/BF01270384"},{"key":"258_CR20","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1973). Die Berechnungskomplexit\u00e4t Von Elementarsymmetrischen\nFunktionen Und Von Interpolationskoeffizienten. Numerische\nMathematik 20(3), 238\u2013251. ISSN 0029-599X. URL http:\/\/dx.doi.org\/10.1007\/BF01436566.","DOI":"10.1007\/BF01436566"},{"key":"258_CR21","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1975). On Non-linear Lower Bounds in Computational\nComplexity. In Proceedings of the 7th Annual ACM Symposium\non Theory of Computing (STOC 1975), William C. Rounds, Nancy\nMartin, Jack W. Carlyle & Michael A. Harrison, editors, 45\u2013\n53. ACM. URL https:\/\/doi.org\/10.1145\/800116.803752.","DOI":"10.1145\/800116.803752"},{"key":"258_CR22","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1977). Graph-Theoretic Arguments in Low-Level\nComplexity. In Proceedings of the 2nd International Symposium on the\nMathematical Foundations of Computer Science (MFCS 1977), Jozef\nGruska, editor, volume 53 of Lecture Notes in Computer Science, 162\u2013\n176. Springer. URL https:\/\/doi.org\/10.1007\/3-540-08353-7_135.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"258_CR23","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). Completeness Classes in Algebra. In Proceedings\nof the 11th Annual ACM Symposium on Theory of Computing\n(STOC 1979), 249\u2013261.","DOI":"10.1145\/800135.804419"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00258-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00258-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00258-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T03:06:45Z","timestamp":1733454405000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00258-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,31]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["258"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00258-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,31]]},"assertion":[{"value":"2 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}