{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T13:31:50Z","timestamp":1744291910037,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030794156"},{"type":"electronic","value":"9783030794163"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_9","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"147-169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Limitations of Sums of Bounded Read Formulas and ABPs"],"prefix":"10.1007","author":[{"given":"Purnata","family":"Ghosal","sequence":"first","affiliation":[]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, 25\u201328 October 2008, Philadelphia, PA, USA, pages 67\u201375. IEEE Computer Society (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.32","DOI":"10.1109\/FOCS.2008.32"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Kumar, M., Volk, B.L.: Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. Comb. 40(2):149\u2013178 (2020). https:\/\/doi.org\/10.1007\/s00493-019-4009-0","DOI":"10.1007\/s00493-019-4009-0"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Anderson, M., van Melkebeek, D., Volkovich, I.: Derandomizing polynomial identity testing for multilinear constant-read formulae. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, 8\u201310 June 2011, pp. 273\u2013282. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/CCC.2011.18","DOI":"10.1109\/CCC.2011.18"},{"key":"9_CR4","unstructured":"Arvind, V., Raja, S.: Some lower bound results for set-multilinear arithmetic computations. Chicago J. Theor. Comput. Sci. (2016). http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/6\/contents.html"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci. 22, 317\u2013330 (1983). https:\/\/doi.org\/10.1016\/0304-3975(83)90110-X","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput. 21(1), 54\u201358 (1992). https:\/\/doi.org\/10.1137\/0221006","DOI":"10.1137\/0221006"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Biedl, T.C., Demaine, E.D., Duncan, RC., Fleischer, A., Kobourov, S.: Tight bounds on maximal and maximum matchings. Discret. Math. 285(1\u20133), 7\u201315 (2004). https:\/\/doi.org\/10.1016\/j.disc.2004.05.003","DOI":"10.1016\/j.disc.2004.05.003"},{"key":"9_CR8","doi-asserted-by":"publisher","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. ACM 21(2), 201\u2013206 (1974). https:\/\/doi.org\/10.1145\/321812.321815","DOI":"10.1145\/321812.321815"},{"key":"9_CR9","doi-asserted-by":"publisher","unstructured":"B\u00fcrgisser, P.: Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics, vol. 1. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/978-3-662-04179-6","DOI":"10.1007\/978-3-662-04179-6"},{"key":"9_CR10","unstructured":"Chatterjee, P., Kumar, M., She, A., Volk, B.L.: A quadratic lower bound for algebraic branching programs. In: Saraf, S. (eds.) 35th Computational Complexity Conference, CCC 2020, 28\u201331 July 2020, Saarbr\u00fccken, Germany (Virtual Conference). LIPIcs, vol. 169, pp. 2:1\u20132:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.2"},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Chillara, S., Engels, C., Limaye, N., Srinivasan, A near-optimal depth-hierarchy theorem for small-depth multilinear circuits. In: Thorup, M., (eds.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7\u20139 October 2018, pp. 934\u2013945. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00092","DOI":"10.1109\/FOCS.2018.00092"},{"key":"9_CR12","unstructured":"Chung, F.R.K.: Separator theorems and their applications. Forschungsinst. f\u00fcr Diskrete Mathematik (1989). http:\/\/www.math.ucsd.edu\/~fan\/mypaps\/fanpap\/117separatorthms.pdf"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Dvir, Z., Malod, G., Perifel, S., Yehudayoff, A.: Separating multilinear branching programs and formulas. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 615\u2013624. ACM (2012). https:\/\/doi.org\/10.1145\/2213977.2214034","DOI":"10.1145\/2213977.2214034"},{"key":"9_CR14","doi-asserted-by":"publisher","unstructured":"Grigoriev, D., Karpinski, M.: An exponential lower bound for depth 3 arithmetic circuits. In: Vitter, J.S. (eds.) Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23\u201326 May 1998, pp. 577\u2013582. ACM (1998). https:\/\/doi.org\/10.1145\/276698.276872","DOI":"10.1145\/276698.276872"},{"key":"9_CR15","doi-asserted-by":"publisher","unstructured":"Grigoriev, D., Razborov, A.A.: Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput. 10(6), 465\u2013487 (2000). https:\/\/doi.org\/10.1007\/s002009900021","DOI":"10.1007\/s002009900021"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-540-85238-4_33","volume-title":"Mathematical Foundations of Computer Science 2008","author":"MJ Jansen","year":"2008","unstructured":"Jansen, M.J.: Lower bounds for syntactically multilinear algebraic branching programs. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 407\u2013418. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85238-4_33"},{"key":"9_CR17","doi-asserted-by":"publisher","unstructured":"Jansen, M.J., Qiao, Y., Sarma, J.: Deterministic black-box identity testing $$pi$$-ordered algebraic branching programs. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, 15\u201318 December 2010, Chennai, India, pp. 296\u2013307 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2010.296","DOI":"10.4230\/LIPIcs.FSTTCS.2010.296"},{"key":"9_CR18","doi-asserted-by":"publisher","unstructured":"Jerrum, M., Snir, M.: Some exact complexity results for straight-line computations over semirings. J. ACM 29(3), 874\u2013897 (1982). https:\/\/doi.org\/10.1145\/322326.322341","DOI":"10.1145\/322326.322341"},{"key":"9_CR19","doi-asserted-by":"publisher","unstructured":"Kayal, N., Nair, V., Saha, C.: Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth three circuits. In: Ollinger, N., Vollmer, H. (eds.) 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, 17\u201320 February 2016, Orl\u00e9ans, France, volume 47 of LIPIcs, pp. 46:1\u201346:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.46","DOI":"10.4230\/LIPIcs.STACS.2016.46"},{"key":"9_CR20","unstructured":"Kayal, N., Saha, C., Tavenas, S.: An almost cubic lower bound for depth three arithmetic circuits. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 23, no. 6 (2016). http:\/\/eccc.hpi-web.de\/report\/2016\/006"},{"key":"9_CR21","doi-asserted-by":"publisher","unstructured":"Kumar, M.: A quadratic lower bound for homogeneous algebraic branching programs. Comput. Complex. 28(3), 409\u2013435 (2019). https:\/\/doi.org\/10.1007\/s00037-019-00186-3","DOI":"10.1007\/s00037-019-00186-3"},{"key":"9_CR22","doi-asserted-by":"publisher","unstructured":"Mahajan, M., Tawari, A.: Sums of read-once formulas: How many summands are necessary? Theor. Comput. Sci. 708, 34\u201345 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.10.019","DOI":"10.1016\/j.tcs.2017.10.019"},{"key":"9_CR23","doi-asserted-by":"publisher","unstructured":"Malod, G., Portier, N.: Characterizing valiant\u2019s algebraic complexity classes. J. Complex. 24(1), 16\u201338 (2008). https:\/\/doi.org\/10.1016\/j.jco.2006.09.006","DOI":"10.1016\/j.jco.2006.09.006"},{"key":"9_CR24","doi-asserted-by":"publisher","unstructured":"Minahan, D., Volkovich, I.: Complete derandomization of identity testing and reconstruction of read-once formulas. TOCT 10(3), 10:1\u201310:11 (2018). https:\/\/doi.org\/10.1145\/3196836","DOI":"10.1145\/3196836"},{"key":"9_CR25","doi-asserted-by":"publisher","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005). https:\/\/doi.org\/10.1017\/CBO9780511813603","DOI":"10.1017\/CBO9780511813603"},{"key":"9_CR26","doi-asserted-by":"publisher","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: Koutsougeras, C., Vitter, J.S. (eds.) Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, Louisiana, USA, 5\u20138 May 1991, pp. 410\u2013418. ACM (1991). https:\/\/doi.org\/10.1145\/103418.103462","DOI":"10.1145\/103418.103462"},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/978-3-319-94776-1_58","volume-title":"Computing and Combinatorics","author":"C Ramya","year":"2018","unstructured":"Ramya, C., Rao, B.V.R.: Lower bounds for special cases of syntactic multilinear ABPs. In: Wang, L., Zhu, D. (eds.) COCOON 2018. LNCS, vol. 10976, pp. 701\u2013712. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94776-1_58"},{"key":"9_CR28","doi-asserted-by":"publisher","unstructured":"Ramya, C., Raghavendra Rao, B.V.: Lower bounds for multilinear order-restricted ABPs. In: Rossmanith, P., Heggernes, P., Katoen, J.-P . (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 26\u201330 August 2019. LIPIcs, vol. 138, pp. 52:1\u201352:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.52","DOI":"10.4230\/LIPIcs.MFCS.2019.52"},{"key":"9_CR29","doi-asserted-by":"publisher","unstructured":"Ramya, C., Raghavendra Rao, B.V.: Lower bounds for sum and sum of products of read-once formulas. TOCT 11(2), 10:1\u201310:27 (2019.) https:\/\/doi.org\/10.1145\/3313232","DOI":"10.1145\/3313232"},{"key":"9_CR30","doi-asserted-by":"publisher","unstructured":"Raz, R.: Separation of multilinear circuit and formula size. Theory Comput. 2(6), 121\u2013135 (2006). https:\/\/doi.org\/10.4086\/toc.2006.v002a006","DOI":"10.4086\/toc.2006.v002a006"},{"key":"9_CR31","doi-asserted-by":"publisher","unstructured":"Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2), 8:1\u20138:17 (2009). https:\/\/doi.org\/10.1145\/1502793.1502797","DOI":"10.1145\/1502793.1502797"},{"key":"9_CR32","doi-asserted-by":"publisher","unstructured":"Raz, R., Yehudayoff, A.: Balancing syntactically multilinear arithmetic circuits. Comput. Complex. 17(4), 515\u2013535 (2008). https:\/\/doi.org\/10.1007\/s00037-008-0254-0","DOI":"10.1007\/s00037-008-0254-0"},{"key":"9_CR33","unstructured":"Saptharishi, R., Chillara, S., Kumar, M.: A survey of lower bounds in arithmetic circuit complexity. Technical report (2016). https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases"},{"key":"9_CR34","doi-asserted-by":"publisher","unstructured":"Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10(1), 1\u201327 (2001). https:\/\/doi.org\/10.1007\/PL00001609. https:\/\/doi.org\/10.1007\/PL00001609","DOI":"10.1007\/PL00001609 10.1007\/PL00001609"},{"key":"9_CR35","doi-asserted-by":"publisher","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Foundations and Trends Theoret. Comput. Sci. 5(3\u20134), 207\u2013388 (2010). https:\/\/doi.org\/10.1561\/0400000039. https:\/\/doi.org\/10.1561\/0400000039","DOI":"10.1561\/0400000039 10.1561\/0400000039"},{"key":"9_CR36","unstructured":"Srinivasan, S.: Strongly exponential separation between monotone VP and monotone VNP. CoRR, abs\/1903.01630 (2019). http:\/\/arxiv.org\/abs\/1903.01630"},{"issue":"1","key":"9_CR37","first-page":"116","volume":"75","author":"S Toda","year":"1992","unstructured":"Toda, S.: Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Syst. 75(1), 116\u2013124 (1992)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"9_CR38","doi-asserted-by":"publisher","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"9_CR39","doi-asserted-by":"publisher","unstructured":"Volkovich, I.: Characterizing arithmetic read-once formulae. TOCT 8(1), 2:1\u20132:19 (2016). https:\/\/doi.org\/10.1145\/2858783","DOI":"10.1145\/2858783"},{"key":"9_CR40","doi-asserted-by":"publisher","unstructured":"Yehudayoff, A.: Separating monotone VP and VNP. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23\u201326 June 2019, pp. 425\u2013429. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316311","DOI":"10.1145\/3313276.3316311"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:21:28Z","timestamp":1623972088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}