{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:06Z","timestamp":1750220466480,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CHE-PBC"},{"name":"Institute Post Doctoral Fellowship at IIT Bombay"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            In this article, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which the polynomial computed at every node has a bound on the individual degree of\n            <jats:italic>r<\/jats:italic>\n            \u2265 1 with respect to all its variables (referred to as multi-\n            <jats:italic>r<\/jats:italic>\n            -ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better bounds as the value of\n            <jats:italic>r<\/jats:italic>\n            increases.\n          <\/jats:p>\n          <jats:p>\n            Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree\n            <jats:italic>r<\/jats:italic>\n            computing an explicit multilinear polynomial on\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            variables and degree\n            <jats:italic>d<\/jats:italic>\n            must have size at least (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>1.1<\/jats:sup>\n            )\n            <jats:sup>\n              \u03a9(\u221a\n              <jats:italic>d<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            . This bound, however, deteriorates as the value of\n            <jats:italic>r<\/jats:italic>\n            increases. It is a natural question to ask if we can prove a bound that does not deteriorate as the value of\n            <jats:italic>r<\/jats:italic>\n            increases, or a bound that holds for a\n            <jats:italic>larger<\/jats:italic>\n            regime of\n            <jats:italic>r<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            In this article, we prove a lower bound that does not deteriorate with increasing values of\n            <jats:italic>r<\/jats:italic>\n            , albeit for a specific instance of\n            <jats:italic>d<\/jats:italic>\n            =\n            <jats:italic>d<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) but for a\n            <jats:italic>wider<\/jats:italic>\n            range of\n            <jats:italic>r<\/jats:italic>\n            . Formally, for all large enough integers\n            <jats:italic>n<\/jats:italic>\n            and a small constant \u03b7, we show that there exists an explicit polynomial on\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            variables and degree \u0398 (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) such that any depth four circuit of bounded individual degree\n            <jats:italic>r<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            \u03b7 must have size at least exp(\u03a9(log\n            <jats:italic>2<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            )). This\n            <jats:italic>improvement<\/jats:italic>\n            is obtained by suitably adapting the complexity measure of Kayal et\u00a0al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et\u00a0al. (SIAM J. Computing, 2017).\n          <\/jats:p>","DOI":"10.1145\/3460952","type":"journal-article","created":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T16:04:05Z","timestamp":1626624245000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Computing Multilinear Polynomials Using Multi-\n            <i>r<\/i>\n            -ic Depth Four Circuits"],"prefix":"10.1145","volume":"13","author":[{"given":"Suryajith","family":"Chillara","sequence":"first","affiliation":[{"name":"CRI, University of Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"volume-title":"Proceedings of Foundations of Computer Science (FOCS\u201908)","year":"2008","author":"Agrawal Manindra","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","volume-title":"CCC (LIPIcs)","volume":"102","author":"Alon Noga","year":"2018"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00092"},{"key":"e_1_2_1_5_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"13","author":"Chillara Suryajith","year":"2018"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1191567"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00185-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990280"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_2_1_10_1","unstructured":"Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2019. Essential Coding Theory. https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/.  Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2019. Essential Coding Theory. https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/."},{"key":"e_1_2_1_11_1","first-page":"907","article-title":"Improved lower bound for multi-r-ic depth four circuits as a function of the number of input variables","volume":"83","author":"Hegde Sumant","year":"2017","journal-title":"Proc. Indian Nat. Sci. Acad."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0007-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214050"},{"key":"e_1_2_1_14_1","first-page":"81","article-title":"An exponential lower bound for the sum of powers of bounded degree polynomials","volume":"19","author":"Kayal Neeraj","year":"2012","journal-title":"Elect. Coll. Comput. Complex. (ECCC)"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591823"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002423"},{"volume-title":"Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","year":"2016","author":"Kayal Neeraj","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9742-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591847"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a016"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_22_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"15","author":"Kumar Mrinal","year":"2019"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/140999335"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"volume-title":"Multilinear- Multilinear-. In Proceedings of Foundations of Computer Science (FOCS\u201904)","year":"2004","author":"Raz Ran","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0254-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_30_1","unstructured":"Ramprasad Saptharishi. 2019. A survey of lower bounds in arithmetic circuit complexity Version 8.0.4. (2019). Github Survey. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/.  Ramprasad Saptharishi. 2019. A survey of lower bounds in arithmetic circuit complexity Version 8.0.4. (2019). Github Survey. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/."},{"key":"e_1_2_1_31_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02252909"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460952","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:22Z","timestamp":1750193302000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3460952"],"URL":"https:\/\/doi.org\/10.1145\/3460952","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"2021-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}