{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T05:27:59Z","timestamp":1759814879894,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MATRICS grant of the Science and Engineering Research Board, DST, India","award":["MTR\/2019\/001633"],"award-info":[{"award-number":["MTR\/2019\/001633"]}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Tata Consultancy Services Research Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451069","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"786-799","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Lower bounds for monotone arithmetic circuits via communication complexity"],"prefix":"10.1145","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}]},{"given":"Rajit","family":"Datta","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0078-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_3_2_1_5_1","first-page":"2006","article-title":"Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order","volume":"2","author":"Bourgain J.","year":"2006","unstructured":"J. Bourgain, A. A. Glibichuk, and S. V. Konyagin. 2006. Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order. Journal of London Mathematical Society, 2, 2006. Pages 380\u2013398.","journal-title":"Journal of London Mathematical Society"},{"key":"e_1_3_2_1_6_1","first-page":"2020","article-title":"Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity","volume":"27","author":"Chattopadhyay Arkadev","year":"2020","unstructured":"Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. 2020. Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity. Electron. Colloquium Comput. Complex., 27, 2020. Pages 166. https:\/\/eccc.weizmann.ac.il\/report\/2020\/166","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396695"},{"key":"e_1_3_2_1_8_1","volume-title":"Igor Carboni Oliviera, and Rocco A. Servedio","author":"Chen Xi","year":"2017","unstructured":"Xi Chen, Igor Carboni Oliviera, and Rocco A. Servedio. 2017. Addition is exponentially harder than counting for shallow monotone circuits. In STOC. Pages 665\u2013677."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1070\/SM2012v203n10ABEH004270"},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Adventures in Monotone Complexity and \\text TFNP","volume":"38","author":"G\u00f6\u00f6s Mika","year":"2019","unstructured":"Mika G\u00f6\u00f6s, Pritish Kamath, Robert Robere, and Dmitry Sokolov. 2019. Adventures in Monotone Complexity and \\text TFNP. In ITCS. Pages 38:1\u201338:19.","journal-title":"ITCS. Pages"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335349"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-020-00196-6"},{"key":"e_1_3_2_1_14_1","volume-title":"Computational Complexity Conference. Pages 10\u201314","author":"Amir Yehudayoff Pavel","year":"2013","unstructured":"Pavel Hrube\\v s and Amir Yehudayoff. 2013. Formulas are exponentially stronger than monotone circuits in non-commutative setting. In Computational Complexity Conference. Pages 10\u201314."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322341"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055478"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050062"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.013"},{"key":"e_1_3_2_1_22_1","first-page":"6","article-title":"A lower bound on the monotone network complexity of the logical permanent","volume":"37","author":"Razborov Alexander A.","year":"1985","unstructured":"Alexander A. Razborov. 1985. A lower bound on the monotone network complexity of the logical permanent. Mathematicheskie Garnetki, 37, 6, 1985. Pages 887\u2013900.","journal-title":"Mathematicheskie Garnetki"},{"key":"e_1_3_2_1_23_1","first-page":"1985","article-title":"Lower bounds for the monotone complexity of some Boolean Functions","volume":"281","author":"Razborov Alexander A.","year":"1985","unstructured":"Alexander A. Razborov. 1985. Lower bounds for the monotone complexity of some Boolean Functions. Dokl. Ak. Nauk. SSSR, 281, 1985. Pages 354\u2013357.","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_25_1","volume-title":"30th Conference on Computational Complexity, CCC 2015","author":"Rossman Benjamin","year":"2015","unstructured":"Benjamin Rossman. 2015. Correlation Bounds Against Monotone NC\\^1. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA. LIPIcs. 33, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Pages 392\u2013411."},{"key":"e_1_3_2_1_26_1","unstructured":"Eli Shamir and Marc Snir. 1977. Lower Bounds on the number of multiplications and additions in monotone computations."},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"On the depth complexity of formulas","volume":"13","author":"Shamir Eli","year":"1980","unstructured":"Eli Shamir and Marc Snir. 1980. On the depth complexity of formulas. Theory of Computing Systems, 13, 1, 1980. Pages 301\u2013322.","journal-title":"Theory of Computing Systems"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_29_1","first-page":"2019","article-title":"Strongly Exponential Separation Between Monotone VP and Monotone VNP","volume":"26","author":"Srinivasan Srikanth","year":"2019","unstructured":"Srikanth Srinivasan. 2019. Strongly Exponential Separation Between Monotone VP and Monotone VNP. Electron. Colloquium Comput. Complex., 26, 2019. Pages 32. https:\/\/eccc.weizmann.ac.il\/report\/2019\/032","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055408"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122563"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90060-2"},{"key":"e_1_3_2_1_35_1","volume-title":"Counting Labelled Trees. Canadian Mathematical Congress","author":"Moon J","year":"1970","unstructured":"Moon J W. 1970. Counting Labelled Trees. Canadian Mathematical Congress, Montreal, 1970."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316311"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451069","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":36,"alternative-id":["10.1145\/3406325.3451069","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451069","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}