{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:46Z","timestamp":1750694806518,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1909429"],"award-info":[{"award-number":["CCF-1909429"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585187","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1076-1089","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic"],"prefix":"10.1145","author":[{"given":"Rahul","family":"Ilango","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Jiatu","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}]},{"given":"R. Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"TR23-015","author":"Aaronson Scott","year":"2023","unstructured":"Scott Aaronson , Harry Buhrman , and William Kretschmer . 2023. A Qubit , a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex ., TR23-015 ( 2023 ), https:\/\/eccc.weizmann.ac.il\/report\/2023\/015 Scott Aaronson, Harry Buhrman, and William Kretschmer. 2023. A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex., TR23-015 (2023), https:\/\/eccc.weizmann.ac.il\/report\/2023\/015"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","key":"e_1_3_2_1_3_1","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.1145\/22145.22192"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56784-2_26"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0242-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"volume-title":"Bounded arithmetic","author":"Buss Samuel R","key":"e_1_3_2_1_12_1","unstructured":"Samuel R Buss . 1985. Bounded arithmetic . Princeton University . Samuel R Buss. 1985. Bounded arithmetic. Princeton University."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.37"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-16(2:12)2020"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-019-00681-y"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00080"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00010"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_20"},{"key":"e_1_3_2_1_20_1","volume-title":"Proc. Logic, Methodology and Philosophy of Science, 24\u201330","author":"Cobham Alan","year":"1965","unstructured":"Alan Cobham . 1965 . The intrinsic computational difficulty of functions . Proc. Logic, Methodology and Philosophy of Science, 24\u201330 . Alan Cobham. 1965. The intrinsic computational difficulty of functions. Proc. Logic, Methodology and Philosophy of Science, 24\u201330."},{"volume-title":"Logical foundations of proof complexity. 11","author":"Cook Stephen","key":"e_1_3_2_1_21_1","unstructured":"Stephen Cook and Phuong Nguyen . 2010. Logical foundations of proof complexity. 11 , Cambridge University Press Cambridge . Stephen Cook and Phuong Nguyen. 2010. Logical foundations of proof complexity. 11, Cambridge University Press Cambridge."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803756"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_3_2_1_24_1","volume-title":"Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR, abs\/2303.05044","author":"Gajulapalli Karthik","year":"2023","unstructured":"Karthik Gajulapalli , Alexander Golovnev , Satyajeet Nagargoje , and Sidhant Saraogi . 2023. Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR, abs\/2303.05044 ( 2023 ), https:\/\/doi.org\/10.48550\/arXiv.2303.05044 arXiv:2303.05044. 10.48550\/arXiv.2303.05044 Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. 2023. Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. CoRR, abs\/2303.05044 (2023), https:\/\/doi.org\/10.48550\/arXiv.2303.05044 arXiv:2303.05044."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/14095772X"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488667"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"e_1_3_2_1_28_1","first-page":"73","article-title":"Private Coins versus Public Coins in Interactive Proof","volume":"5","author":"Goldwasser Shafi","year":"1989","unstructured":"Shafi Goldwasser and Michael Sipser . 1989 . Private Coins versus Public Coins in Interactive Proof Systems. Adv. Comput. Res. , 5 (1989), 73 \u2013 90 . Shafi Goldwasser and Michael Sipser. 1989. Private Coins versus Public Coins in Interactive Proof Systems. Adv. Comput. Res., 5 (1989), 73\u201390.","journal-title":"Systems. Adv. Comput. Res."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.20"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.7"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00100"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451093"},{"key":"e_1_3_2_1_34_1","unstructured":"Aayush Jain Huijia Lin and Amit Sahai. 2022. Personal Communication. \t\t\t\t  Aayush Jain Huijia Lin and Amit Sahai. 2022. Personal Communication."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"volume-title":"Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation. Ph. D. thesis","author":"Je\u0159\u00e1bek Emil","key":"e_1_3_2_1_37_1","unstructured":"Emil Je\u0159\u00e1bek . 2005. Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation. Ph. D. thesis , Faculty of Mathematics and Physics, Charles University , Prague. Emil Je\u0159\u00e1bek. 2005. Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation. Ph. D. thesis, Faculty of Mathematics and Physics, Charles University, Prague."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm017"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1245158087"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.17"},{"volume-title":"Computer Scientists Achieve \u2018Crown Jewel","author":"Klarreich Erica","key":"e_1_3_2_1_43_1","unstructured":"Erica Klarreich . 2020. Computer Scientists Achieve \u2018Crown Jewel \u2019 of Cryptography. Quanta Magazine , Nov. Erica Klarreich. 2020. Computer Scientists Achieve \u2018Crown Jewel\u2019 of Cryptography. Quanta Magazine, Nov."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.44"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90081-2"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207166808803030"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/15m1048549"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00051"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.37"},{"volume-title":"Bounded arithmetic, propositional logic, and complexity theory (Encyclopedia of mathematics and its applications","author":"Kraj\u00ed\u010dek Jan","key":"e_1_3_2_1_51_1","unstructured":"Jan Kraj\u00ed\u010dek . 1995. Bounded arithmetic, propositional logic, and complexity theory (Encyclopedia of mathematics and its applications , Vol. 60). Cambridge University Press. isbn:978-0-521-45205- 2 Jan Kraj\u00ed\u010dek. 1995. Bounded arithmetic, propositional logic, and complexity theory (Encyclopedia of mathematics and its applications, Vol. 60). Cambridge University Press. isbn:978-0-521-45205-2"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061311000979"},{"volume-title":"Proof complexity. 170","author":"Kraj\u00ed\u010dek Jan","key":"e_1_3_2_1_53_1","unstructured":"Jan Kraj\u00ed\u010dek . 2019. Proof complexity. 170 , Cambridge University Press . Jan Kraj\u00ed\u010dek. 2019. Proof complexity. 170, Cambridge University Press."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446207"},{"key":"e_1_3_2_1_55_1","volume-title":"TR22-120","author":"Kraj\u00edcek Jan","year":"2022","unstructured":"Jan Kraj\u00edcek . 2022. On the existence of strong proof complexity generators. Electron. Colloquium Comput. Complex ., TR22-120 ( 2022 ), https:\/\/eccc.weizmann.ac.il\/report\/2022\/120 Jan Kraj\u00edcek. 2022. On the existence of strong proof complexity generators. Electron. Colloquium Comput. Complex., TR22-120 (2022), https:\/\/eccc.weizmann.ac.il\/report\/2022\/120"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-13(1:4)2017"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(3:5)2012"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0197-7"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"volume-title":"Combinatorics in bounded arithmetic. Ph. D. Dissertation","author":"Ojakian Kerry","key":"e_1_3_2_1_61_1","unstructured":"Kerry Ojakian . 2004. Combinatorics in bounded arithmetic. Ph. D. Dissertation . Carnegie Mellon University . Kerry Ojakian. 2004. Combinatorics in bounded arithmetic. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.08.004"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(2:8)2015"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451117"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00067"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1030108"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"volume-title":"Introduction to the theory of computation","author":"Sipser Michael","key":"e_1_3_2_1_69_1","unstructured":"Michael Sipser . 1997. Introduction to the theory of computation . PWS Publishing Company . Michael Sipser. 1997. Introduction to the theory of computation. PWS Publishing Company."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_19"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22963-3_7"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585187","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":72,"alternative-id":["10.1145\/3564246.3585187","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585187","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}