{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:57:33Z","timestamp":1742918253084,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":39,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819723393"},{"type":"electronic","value":"9789819723409"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-2340-9_30","type":"book-chapter","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:01:51Z","timestamp":1714690911000},"page":"355-366","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for\u00a0the\u00a0Sum of\u00a0Small-Size Algebraic Branching Programs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6920-4998","authenticated-orcid":false,"given":"C. S.","family":"Bhargav","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0572-3721","authenticated-orcid":false,"given":"Prateek","family":"Dwivedi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6931-898X","authenticated-orcid":false,"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"issue":"17","key":"30_CR1","doi-asserted-by":"publisher","first-page":"8107","DOI":"10.1073\/pnas.1901272116","volume":"116","author":"M Agrawal","year":"2019","unstructured":"Agrawal, M., Ghosh, S., Saxena, N.: Bootstrapping variables in algebraic circuits. Proc. Natl. Acad. Sci. U.S.A. 116(17), 8107\u20138118 (2019). https:\/\/doi.org\/10.1073\/pnas.1901272116","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"30_CR2","doi-asserted-by":"publisher","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 67\u201375 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.32","DOI":"10.1109\/FOCS.2008.32"},{"key":"30_CR3","doi-asserted-by":"publisher","unstructured":"Anderson, M., Forbes, M.A., Saptharishi, R., Shpilka, A., Volk, B.L.: Identity testing and lower bounds for read-k oblivious algebraic branching programs. ACM Trans. Comput. Theory 10(1), 3:1\u20133:30 (2018). https:\/\/doi.org\/10.1145\/3170709","DOI":"10.1145\/3170709"},{"key":"30_CR4","doi-asserted-by":"publisher","unstructured":"Arvind, V., Raja, S.: Some lower bound results for set-multilinear arithmetic computations. Chic. J. Theor. Comput. Sci. pp. Art. 6, 26 (2016). https:\/\/doi.org\/10.4086\/cjtcs.2016.006","DOI":"10.4086\/cjtcs.2016.006"},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W Baur","year":"1983","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci. 22(3), 317\u2013330 (1983). https:\/\/doi.org\/10.1016\/0304-3975(83)90110-X","journal-title":"Theor. Comput. Sci."},{"key":"30_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory, Algorithms and Computation in Mathematics","author":"P B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory, Algorithms and Computation in Mathematics, vol. 7. Springer, Berlin (2000). https:\/\/doi.org\/10.1007\/978-3-662-04179-6"},{"key":"30_CR7","doi-asserted-by":"publisher","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol.\u00a0315. Springer, Berlin (1997). https:\/\/doi.org\/10.1007\/978-3-662-03338-8, with the collaboration of Thomas Lickteig","DOI":"10.1007\/978-3-662-03338-8"},{"key":"30_CR8","doi-asserted-by":"publisher","unstructured":"Chatterjee, P., Kumar, M., She, A., Volk, B.L.: Quadratic lower bounds for algebraic branching programs and formulas. Comput. Complexity 31(2), Paper No. 8, 54 (2022). https:\/\/doi.org\/10.1007\/s00037-022-00223-8","DOI":"10.1007\/s00037-022-00223-8"},{"key":"30_CR9","unstructured":"Chatterjee, P., Kush, D., Saraf, S., Shpilka, A.: Lower bounds for set-multilinear branching programs (2024). https:\/\/arxiv.org\/abs\/2312.15874, preprint"},{"key":"30_CR10","doi-asserted-by":"publisher","unstructured":"Chen, X., Kayal, N., Wigderson, A.: Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Comput. Sci. 6(1-2), 1\u2013138 (2010). https:\/\/doi.org\/10.1561\/0400000043","DOI":"10.1561\/0400000043"},{"key":"30_CR11","doi-asserted-by":"publisher","unstructured":"Dvir, Z., Malod, G., Perifel, S., Yehudayoff, A.: Separating multilinear branching programs and formulas. In: Proceedings of the 2012 ACM Symposium on Theory of Computing, STOC 2012, pp. 615\u2013623. ACM, New York (2012). https:\/\/doi.org\/10.1145\/2213977.2214034","DOI":"10.1145\/2213977.2214034"},{"key":"30_CR12","doi-asserted-by":"publisher","unstructured":"Forbes, M.A., Shpilka, A.: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, Los Alamitos, CA, pp. 243\u2013252. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.34","DOI":"10.1109\/FOCS.2013.34"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Forbes, M.A.: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. ProQuest LLC, Ann Arbor, MI, thesis (Ph.D.)\u2013Massachusetts Institute of Technology (2014)","DOI":"10.1109\/FOCS.2013.34"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-030-79416-3_9","volume-title":"Computer Science - Theory and Applications","author":"P Ghosal","year":"2021","unstructured":"Ghosal, P., Rao, B.V.R.: Limitations of sums of bounded read formulas and ABPs. In: Santhanam, R., Musatov, D. (eds.) CSR 2021. LNCS, vol. 12730, pp. 147\u2013169. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79416-3_9"},{"key":"30_CR15","unstructured":"Grochow, J.: Degree restriction for polynomials in $$\\sf VP$$. Theoretical Computer Science Stack Exchange (2013). https:\/\/cstheory.stackexchange.com\/q\/19268"},{"issue":"2","key":"30_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1137\/20M1347395","volume":"51","author":"Z Guo","year":"2022","unstructured":"Guo, Z., Kumar, M., Saptharishi, R., Solomon, N.: Derandomization from algebraic hardness. SIAM J. Comput. 51(2), 315\u2013335 (2022). https:\/\/doi.org\/10.1137\/20M1347395","journal-title":"SIAM J. Comput."},{"issue":"3","key":"30_CR17","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1137\/140957123","volume":"45","author":"A Gupta","year":"2016","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: a chasm at depth 3. SIAM J. Comput. 45(3), 1064\u20131079 (2016). https:\/\/doi.org\/10.1137\/140957123","journal-title":"SIAM J. Comput."},{"issue":"4","key":"30_CR18","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.1007\/S00224-016-9742-9","volume":"61","author":"N Kayal","year":"2017","unstructured":"Kayal, N., Saha, C.: Multi-k-ic depth three circuit lower bound. Theory Comput. Syst. 61(4), 1237\u20131251 (2017). https:\/\/doi.org\/10.1007\/S00224-016-9742-9","journal-title":"Theory Comput. Syst."},{"key":"30_CR19","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. Theor. Comput. Sci. 448, 56\u201365 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.041","journal-title":"Theor. Comput. Sci."},{"key":"30_CR20","unstructured":"Kumar, M., Saptharishi, R.: Hardness-randomness tradeoffs for algebraic computation. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 3(129), 56\u201387 (2019). http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/591\/599"},{"key":"30_CR21","doi-asserted-by":"publisher","unstructured":"Kumar, M., Saptharishi, R., Tengse, A.: Near-optimal bootstrapping of hitting sets for algebraic circuits. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, pp. 639\u2013646. SIAM (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.40","DOI":"10.1137\/1.9781611975482.40"},{"key":"30_CR22","doi-asserted-by":"publisher","unstructured":"Kush, D., Saraf, S.: Near-optimal set-multilinear formula lower bounds. In: 38th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol.\u00a0264, pp. Art. No. 15, 33. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2023). https:\/\/doi.org\/10.4230\/lipics.ccc.2023.15","DOI":"10.4230\/lipics.ccc.2023.15"},{"key":"30_CR23","doi-asserted-by":"publisher","unstructured":"Limaye, N., Srinivasan, S., Tavenas, S.: Superpolynomial lower bounds against low-depth algebraic circuits. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021, Los Alamitos, CA, pp. 804\u2013814. IEEE Computer Society (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00083","DOI":"10.1109\/FOCS52979.2021.00083"},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"Mahajan, M.: Algebraic complexity classes. In: Perspectives in Computational Complexity, Progr. Comput. Sci. Appl. Logic, vol.\u00a026, pp. 51\u201375. Birkh\u00e4user\/Springer, Cham (2014). https:\/\/arxiv.org\/abs\/1307.3863","DOI":"10.1007\/978-3-319-05446-9_4"},{"key":"30_CR25","doi-asserted-by":"publisher","unstructured":"Nisan, N.: Lower bounds for non-commutative computation. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 410\u2013418. Association for Computing Machinery, New York (1991). https:\/\/doi.org\/10.1145\/103418.103462","DOI":"10.1145\/103418.103462"},{"issue":"3","key":"30_CR26","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N Nisan","year":"1996","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complex. 6(3), 217\u2013234 (1996). https:\/\/doi.org\/10.1007\/BF01294256","journal-title":"Comput. Complex."},{"key":"30_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.10.047","volume":"809","author":"C Ramya","year":"2020","unstructured":"Ramya, C., Raghavendra Rao, B.V.: Lower bounds for special cases of syntactic multilinear ABPs. Theor. Comput. Sci. 809, 1\u201320 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.10.047","journal-title":"Theor. Comput. Sci."},{"key":"30_CR28","doi-asserted-by":"publisher","unstructured":"Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2), Art. 8, 17 (2009). https:\/\/doi.org\/10.1145\/1502793.1502797","DOI":"10.1145\/1502793.1502797"},{"key":"30_CR29","doi-asserted-by":"publisher","unstructured":"Raz, R.: Tensor-rank and lower bounds for arithmetic formulas. J. ACM 60(6), Art. 40, 15 (2013). https:\/\/doi.org\/10.1145\/2535928","DOI":"10.1145\/2535928"},{"issue":"4","key":"30_CR30","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s00037-008-0254-0","volume":"17","author":"R Raz","year":"2008","unstructured":"Raz, R., Yehudayoff, A.: Balancing syntactically multilinear arithmetic circuits. Comput. Complexity 17(4), 515\u2013535 (2008). https:\/\/doi.org\/10.1007\/s00037-008-0254-0","journal-title":"Comput. Complexity"},{"issue":"2","key":"30_CR31","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"R Raz","year":"2009","unstructured":"Raz, R., Yehudayoff, A.: Lower bounds and separations for constant depth multilinear circuits. Comput. Complexity 18(2), 171\u2013207 (2009). https:\/\/doi.org\/10.1007\/s00037-009-0270-8","journal-title":"Comput. Complexity"},{"key":"30_CR32","unstructured":"Saptharishi, R.: A survey of lower bounds in arithmetic circuit complexity. Github Survey (2021). https:\/\/github.com\/dasarpmar\/lowerbounds-survey"},{"key":"30_CR33","unstructured":"Saxena, N.: Progress on polynomial identity testing. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (99), 49\u201379 (2009). https:\/\/www.cse.iitk.ac.in\/users\/nitin\/papers\/pit-survey09.pdf"},{"key":"30_CR34","doi-asserted-by":"crossref","unstructured":"Saxena, N.: Progress on polynomial identity testing-II. In: Perspectives in Computational Complexity, Progr. Comput. Sci. Appl. Logic, vol.\u00a026, pp. 131\u2013146. Birkh\u00e4user\/Springer, Cham (2014). https:\/\/arxiv.org\/abs\/1401.0976","DOI":"10.1007\/978-3-319-05446-9_7"},{"issue":"3\u20134","key":"30_CR35","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A Shpilka","year":"2009","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3\u20134), 207\u2013388 (2009). https:\/\/doi.org\/10.1561\/0400000039","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"30_CR36","doi-asserted-by":"publisher","unstructured":"Strassen, V.: Die Berechnungskomplexit\u00e4t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20, 238\u2013251 (1972\/73). https:\/\/doi.org\/10.1007\/BF01436566","DOI":"10.1007\/BF01436566"},{"key":"30_CR37","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2014.09.004","volume":"240","author":"S Tavenas","year":"2015","unstructured":"Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3. Inform. Comput. 240, 2\u201311 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.09.004","journal-title":"Inform. Comput."},{"key":"30_CR38","doi-asserted-by":"publisher","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), pp. pp 249\u2013261. ACM, New York (1979). https:\/\/doi.org\/10.1145\/800135.804419","DOI":"10.1145\/800135.804419"},{"issue":"4","key":"30_CR39","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"LG Valiant","year":"1983","unstructured":"Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), 641\u2013644 (1983). https:\/\/doi.org\/10.1137\/0212043","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-2340-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:04:12Z","timestamp":1714691052000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-2340-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819723393","9789819723409"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-2340-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tamc2024.comp.polyu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}