{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:06Z","timestamp":1781078166210,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649602","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"620-629","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-1222-7235","authenticated-orcid":false,"given":"Yilei","family":"Chen","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China \/ Shanghai Qi Zhi Institute, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2358-3141","authenticated-orcid":false,"given":"Jiatu","family":"Li","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0029-x"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_26"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_7_1","volume-title":"Help Functions, and the Remote Point Problem","author":"Arvind Vikraman","year":"2010","unstructured":"Vikraman Arvind and Srikanth Srinivasan. 2010. Circuit Lower Bounds, Help Functions, and the Remote Point Problem. In ICS. Tsinghua University Press, 383\u2013396. http:\/\/conference.iiis.tsinghua.edu.cn\/ICS2010\/content\/papers\/30.html"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56784-2_26"},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. In ITCS (LIPIcs, Vol. 151)","volume":"82","author":"Bartusek James","year":"2020","unstructured":"James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry. 2020. Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. In ITCS (LIPIcs, Vol. 151). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 82:1\u201382:39.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00084"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00074"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00009"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1364886"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Yeyuan Chen Yizhi Huang Jiatu Li and Hanlin Ren. 2023. Range Avoidance Remote Point and Hard Partial Truth Table via Satisfying-Pairs Algorithms. In STOC. ACM 1058\u20131066. https:\/\/doi.org\/10.1145\/3564246.3585147 10.1145\/3564246.3585147","DOI":"10.1145\/3564246.3585147"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_20"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.19"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Sanjam Garg Craig Gentry Amit Sahai and Brent Waters. 2013. Witness encryption and its applications. In STOC. ACM 467\u2013476. https:\/\/doi.org\/10.1145\/2488608.2488667 10.1145\/2488608.2488667","DOI":"10.1145\/2488608.2488667"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Craig Gentry Chris Peikert and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In STOC. ACM 197\u2013206. https:\/\/doi.org\/10.1145\/1374376.1374407 10.1145\/1374376.1374407","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276704"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX"},{"key":"e_1_3_2_1_27_1","first-page":"143","article-title":"Almost Optimal Lower Bounds for Small Depth","volume":"5","author":"H\u00e5stad Johan","year":"1989","unstructured":"Johan H\u00e5stad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Adv. Comput. Res., 5 (1989), 143\u2013170.","journal-title":"Circuits. Adv. Comput. Res."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00095"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Yizhi Huang Rahul Ilango and Hanlin Ren. 2023. NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach. In STOC. ACM 1067\u20131075. https:\/\/doi.org\/10.1145\/3564246.3585154 10.1145\/3564246.3585154","DOI":"10.1145\/3564246.3585154"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Rahul Ilango Jiatu Li and R. Ryan Williams. 2023. Indistinguishability Obfuscation Range Avoidance and Bounded Arithmetic. In STOC. ACM 1076\u20131089. https:\/\/doi.org\/10.1145\/3564246.3585187 10.1145\/3564246.3585187","DOI":"10.1145\/3564246.3585187"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo Leonid A. Levin and Michael Luby. 1989. Pseudo-random Generation from one-way functions (Extended Abstracts). In STOC. ACM 12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Aayush Jain Huijia Lin and Amit Sahai. 2021. Indistinguishability obfuscation from well-founded assumptions. In STOC. ACM 60\u201373. https:\/\/doi.org\/10.1145\/3406325.3451093 10.1145\/3406325.3451093","DOI":"10.1145\/3406325.3451093"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.17"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.44"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78524-8_18"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00051"},{"key":"e_1_3_2_1_38_1","first-page":"1","article-title":"Derandomization from Time-Space Tradeoffs. In CCC (LIPIcs, Vol. 234)","volume":"37","author":"Korten Oliver","year":"2022","unstructured":"Oliver Korten. 2022. Derandomization from Time-Space Tradeoffs. In CCC (LIPIcs, Vol. 234). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 37:1\u201337:26.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2208.11642"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press. https:\/\/doi.org\/10.1017\/9781108242066 10.1017\/9781108242066","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Jiatu Li and Tianqi Yang. 2022. 3.1n - o(n) circuit lower bounds for explicit functions. In STOC. ACM 1180\u20131193. https:\/\/doi.org\/10.1145\/3519935.3519976 10.1145\/3519935.3519976","DOI":"10.1145\/3519935.3519976"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00067"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63248-4_8"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","unstructured":"Roman Smolensky. 1987. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In STOC. ACM 77\u201382. https:\/\/doi.org\/10.1145\/28395.28404 10.1145\/28395.28404","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_19"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.95"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22963-3_7"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a017"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:46Z","timestamp":1750178206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":58,"alternative-id":["10.1145\/3618260.3649602","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649602","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}