{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:08Z","timestamp":1750308428699,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"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.3520010","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"962-975","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity"],"prefix":"10.1145","author":[{"given":"Zhiyuan","family":"Fan","sequence":"first","affiliation":[{"name":"Tsinghua University, China"}]},{"given":"Jiatu","family":"Li","sequence":"additional","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.1145\/2554797.2554821"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_3_2_1_3_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_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_42"},{"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-319-57048-8_3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_25"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84259-8_17"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101387893"},{"key":"e_1_3_2_1_10_1","volume-title":"Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. CoRR, abs\/1805.10698","author":"Chen Lijie","year":"2018","unstructured":"Lijie Chen . 2018. Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. CoRR, abs\/1805.10698 ( 2018 ), arxiv:1805.10698. arxiv:1805.10698 Lijie Chen. 2018. Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. CoRR, abs\/1805.10698 (2018), arxiv:1805.10698. arxiv:1805.10698"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.70"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00077"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384283"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451059"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a009"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3404860"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22993-0_25"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.19"},{"volume-title":"On the Complexity of Coding. In Second International Symposium on Information Theory. 177\u2013184","author":"Gelfand S. I.","key":"e_1_3_2_1_20_1","unstructured":"S. I. Gelfand , R. L. Dobrushin , and M. S. Pinsker . 1973 . On the Complexity of Coding. In Second International Symposium on Information Theory. 177\u2013184 . S. I. Gelfand, R. L. Dobrushin, and M. S. Pinsker. 1973. On the Complexity of Coding. In Second International Symposium on Information Theory. 177\u2013184."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715949"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591808"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_27_1","first-page":"2","article-title":"Fooling Constant-Depth Threshold Circuits","volume":"28","author":"Hatami Pooya","year":"2021","unstructured":"Pooya Hatami , William Hoza , Avishay Tal , and Roei Tell . 2021 . Fooling Constant-Depth Threshold Circuits . Electron. Colloquium Comput. Complex. , 28 (2021), 2 . https:\/\/eccc.weizmann.ac.il\/report\/2021\/002 Pooya Hatami, William Hoza, Avishay Tal, and Roei Tell. 2021. Fooling Constant-Depth Threshold Circuits. Electron. Colloquium Comput. Complex., 28 (2021), 2. https:\/\/eccc.weizmann.ac.il\/report\/2021\/002","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.7"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230630"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040202"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167233"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_29"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1048045"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_37"},{"key":"e_1_3_2_1_36_1","first-page":"23","article-title":"3.1n - o(n) Circuit Lower Bounds for Explicit Functions","volume":"28","author":"Li Jiatu","year":"2021","unstructured":"Jiatu Li and Tianqi Yang . 2021 . 3.1n - o(n) Circuit Lower Bounds for Explicit Functions . Electron. Colloquium Comput. Complex. , 28 (2021), 23 . https:\/\/eccc.weizmann.ac.il\/report\/2021\/023 Jiatu Li and Tianqi Yang. 2021. 3.1n - o(n) Circuit Lower Bounds for Explicit Functions. Electron. Colloquium Comput. Complex., 28 (2021), 23. https:\/\/eccc.weizmann.ac.il\/report\/2021\/023","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316396"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2792978"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195887"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335307"},{"key":"e_1_3_2_1_42_1","unstructured":"E.I. Nechiporuk. 1966. On a Boolean function. Soviet Math. Dokl. 999\u20131000.  E.I. Nechiporuk. 1966. On a Boolean function. Soviet Math. Dokl. 999\u20131000."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.27"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00016"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206030"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_3_2_1_48_1","first-page":"598","article-title":"Lower bounds on the size of constant-depth networks over a complete basis with logical addition","volume":"41","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov . 1987 . Lower bounds on the size of constant-depth networks over a complete basis with logical addition . Mathematicheskie Zametki , 41 , 4 (1987), 598 \u2013 607 . Alexander A. Razborov. 1987. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41, 4 (1987), 598\u2013607.","journal-title":"Mathematicheskie Zametki"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683282"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_3_2_1_54_1","first-page":"187","article-title":"A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization","volume":"24","author":"Tell Roei","year":"2017","unstructured":"Roei Tell . 2017 . A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization . Electron. Colloquium Comput. Complex. , 24 (2017), 187 . https:\/\/eccc.weizmann.ac.il\/report\/2017\/187 Roei Tell. 2017. A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization. Electron. Colloquium Comput. Complex., 24 (2017), 187. https:\/\/eccc.weizmann.ac.il\/report\/2017\/187","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188822"},{"key":"e_1_3_2_1_56_1","first-page":"120","article-title":"How to Find Water in the Ocean: A Survey on Quantified Derandomization","volume":"28","author":"Tell Roei","year":"2021","unstructured":"Roei Tell . 2021 . How to Find Water in the Ocean: A Survey on Quantified Derandomization . Electron. Colloquium Comput. Complex. , 28 (2021), 120 . https:\/\/eccc.weizmann.ac.il\/report\/2021\/120 Roei Tell. 2021. How to Find Water in the Ocean: A Survey on Quantified Derandomization. Electron. Colloquium Comput. Complex., 28 (2021), 120. https:\/\/eccc.weizmann.ac.il\/report\/2021\/120","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3078-3"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"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.3520010","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520010","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.3520010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":58,"alternative-id":["10.1145\/3519935.3520010","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520010","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"}}]}}