{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:45:30Z","timestamp":1773996330564,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519976","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1180-1193","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["3.1\n            <i>n<\/i>\n            \u2212\n            <i>o<\/i>\n            (\n            <i>n<\/i>\n            ) circuit lower bounds for explicit functions"],"prefix":"10.1145","author":[{"given":"Jiatu","family":"Li","sequence":"first","affiliation":[{"name":"Tsinghua University, China"}]},{"given":"Tianqi","family":"Yang","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_3_2_1_2_1","first-page":"70","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0 -schemes. Vestnik Moskov","author":"Andreev A. E.","year":"1987","unstructured":"A. E. Andreev . 1987 . On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0 -schemes. Vestnik Moskov . Univ. Ser. 1. Mat. Mekh. , 70 \u2013 73 . A. E. Andreev. 1987. On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0 -schemes. Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 70\u201373.","journal-title":"Univ. Ser. 1. Mat. Mekh."},{"key":"e_1_3_2_1_3_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity - A Modern Approach . Cambridge University Press . isbn:978-0-521-42426-4 http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264 Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. isbn:978-0-521-42426-4 http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/110826254"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90029-4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22993-0_25"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.19"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.04.005"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840755"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.24"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040202"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_29"},{"key":"e_1_3_2_1_15_1","first-page":"21","article-title":"Complexity of the realization of a linear function in the class of \u03c0 -circuits","volume":"9","author":"Khrapchenko VM","year":"1971","unstructured":"VM Khrapchenko . 1971 . Complexity of the realization of a linear function in the class of \u03c0 -circuits . Mathematical Notes of the Academy of Sciences of the USSR , 9 , 1 (1971), 21 \u2013 23 . VM Khrapchenko. 1971. Complexity of the realization of a linear function in the class of \u03c0 -circuits. Mathematical Notes of the Academy of Sciences of the USSR, 9, 1 (1971), 21\u201323.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"V. M. Khrapchenko. 1971. Method of determining lower bounds for the complexity of P-schemes. Mathematical notes of the Academy of Sciences of the USSR 474\u2013479.  V. M. Khrapchenko. 1971. Method of determining lower bounds for the complexity of P-schemes. Mathematical notes of the Academy of Sciences of the USSR 474\u2013479.","DOI":"10.1007\/BF01747074"},{"key":"e_1_3_2_1_17_1","first-page":"44","article-title":"Estimates of the complexity of certain classes of functions","volume":"1","author":"Kloss Boris M.","year":"1965","unstructured":"Boris M. Kloss and Vadim A. Malyshev . 1965 . Estimates of the complexity of certain classes of functions . Vestn. Moskov. Univ. Ser. 1 , 4 (1965), 44 \u2013 51 . Boris M. Kloss and Vadim A. Malyshev. 1965. Estimates of the complexity of certain classes of functions. Vestn. Moskov. Univ. Ser. 1, 4 (1965), 44\u201351.","journal-title":"Vestn. Moskov. Univ. Ser."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380832"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.27"},{"key":"e_1_3_2_1_20_1","first-page":"121","article-title":"Extractors for Affine Sources with Polylogarithmic Entropy","volume":"22","author":"Li Xin","year":"2015","unstructured":"Xin Li . 2015 . Extractors for Affine Sources with Polylogarithmic Entropy . Electron. Colloquium Comput. Complex. , 22 (2015), 121 . http:\/\/eccc.hpi-web.de\/report\/2015\/121 Xin Li. 2015. Extractors for Affine Sources with Polylogarithmic Entropy. Electron. Colloquium Comput. Complex., 22 (2015), 121. http:\/\/eccc.hpi-web.de\/report\/2015\/121","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195887"},{"key":"e_1_3_2_1_22_1","first-page":"765","article-title":"On a Boolean function","volume":"169","author":"Nechiporuk Edward I.","year":"1966","unstructured":"Edward I. Nechiporuk . 1966 . On a Boolean function . Doklady Akademii Nauk. SSSR , 169 , 4 (1966), 765 \u2013 766 . Edward I. Nechiporuk. 1966. On a Boolean function. Doklady Akademii Nauk. SSSR, 169, 4 (1966), 765\u2013766.","journal-title":"Doklady Akademii Nauk. SSSR"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206030"},{"key":"e_1_3_2_1_25_1","unstructured":"A. A. Razborov. 1985. Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR 798\u2013801.  A. A. Razborov. 1985. Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR 798\u2013801."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02246615"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90073-6"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683282"},{"key":"e_1_3_2_1_32_1","unstructured":"B. A. Subbotovskaya. 1961. Realization of linear functions by formulas using \u2228 & ^-. Dokl. Akad. Nauk SSSR 553\u2013555.  B. A. Subbotovskaya. 1961. Realization of linear functions by formulas using \u2228 & ^-. Dokl. Akad. Nauk SSSR 553\u2013555."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220032"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519976","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":38,"alternative-id":["10.1145\/3519935.3519976","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519976","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}