{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:44Z","timestamp":1781031464124,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2312296"],"award-info":[{"award-number":["CCF-2312296"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","award":["NA"],"award-info":[{"award-number":["NA"]}],"id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["NA"],"award-info":[{"award-number":["NA"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRF-NRFI09-0005"],"award-info":[{"award-number":["NRF-NRFI09-0005"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800898","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1925-1936","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Range Avoidance, Arthur-Merlin, and TFNP"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-6968-4059","authenticated-orcid":false,"given":"Surendra","family":"Ghentiyala","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8121-5149","authenticated-orcid":false,"given":"Zeyong","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4511-6984","authenticated-orcid":false,"given":"Noah","family":"Stephens-Davidowitz","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson Harry Buhrman and William Kretschmer. 2024. A Qubit a Coin and an Advice String Walk into a Relational Problem. In ITCS. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.1 10.4230\/LIPIcs.ITCS.2024.1","DOI":"10.4230\/LIPIcs.ITCS.2024.1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai. 1985. Trading group theory for randomness. In STOC. https:\/\/doi.org\/10.1145\/22145.22192 10.1145\/22145.22192","DOI":"10.1145\/22145.22192"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275487"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Lijie Chen Shuichi Hirahara and Hanlin Ren. 2024. Symmetric Exponential Time Requires Near-Maximum Circuit Size. In STOC. https:\/\/doi.org\/10.1145\/3618260.3649624 10.1145\/3618260.3649624","DOI":"10.1145\/3618260.3649624"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Lijie Chen Jiatu Li and Jingxun Liang. 2025. Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin. In STOC. isbn:979-8-4007-1510-5 https:\/\/doi.org\/10.1145\/3717823.3718224 10.1145\/3717823.3718224","DOI":"10.1145\/3717823.3718224"},{"key":"e_1_3_2_1_8_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. https:\/\/doi.org\/10.1145\/3564246.3585147 10.1145\/3564246.3585147","DOI":"10.1145\/3564246.3585147"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Yilei Chen and Jiatu Li. 2024. Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. In STOC. https:\/\/doi.org\/10.1145\/3618260.3649602 10.1145\/3618260.3649602","DOI":"10.1145\/3618260.3649602"},{"key":"e_1_3_2_1_10_1","unstructured":"Eldon Chung Alexander Golovnev Zeyong Li Maciej Obremski Sidhant Saraogi and Noah Stephens-Davidowitz. 2023. The Hardness of Range Avoidance for Randomized Algorithms Implies Minicrypt. 2023\/193\/. issn:1433-8092"},{"key":"e_1_3_2_1_11_1","volume-title":"PCPs for Arthur-Merlin games and communication protocols. Ph. D. Dissertation","author":"Drucker Andrew Donald","unstructured":"Andrew Donald Drucker. 2010. PCPs for Arthur-Merlin games and communication protocols. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Noah Fleming Deniz Imrek and Christophe Marciot. 2025. Provably Total Functions in the Polynomial Hierarchy. In CCC. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2025.28 10.4230\/LIPIcs.CCC.2025.28","DOI":"10.4230\/LIPIcs.CCC.2025.28"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Lance Fortnow. 1987. The complexity of perfect zero-knowledge. In STOC. https:\/\/doi.org\/10.1145\/28395.28418 10.1145\/28395.28418","DOI":"10.1145\/28395.28418"},{"key":"e_1_3_2_1_14_1","first-page":"429","article-title":"On Completeness and Soundness in Interactive Proof Systems","volume":"5","author":"F\u00fcrer Martin","year":"1989","unstructured":"Martin F\u00fcrer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. 1989. On Completeness and Soundness in Interactive Proof Systems. Advances in Computing Research, 5 (1989), 429\u2013442.","journal-title":"Advances in Computing Research"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Karthik Gajulapalli Surendra Ghentiyala Zeyong Li and Sidhant Saraogi. 2026. Downward Self-Reducibility in the Total Function Polynomial Hierarchy. In SODA. https:\/\/doi.org\/10.1137\/1.9781611978971.185 To appear 10.1137\/1.9781611978971.185","DOI":"10.1137\/1.9781611978971.185"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Karthik Gajulapalli Alexander Golovnev Satyajeet Nagargoje and Sidhant Saraogi. 2023. Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. In RANDOM. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2023.65 10.4230\/LIPIcs.APPROX\/RANDOM.2023.65","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.65"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Karthik Gajulapalli Zeyong Li and Ilya Volkovich. 2024. Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies. In FSTTCS. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2024.23 10.4230\/LIPIcs.FSTTCS.2024.23","DOI":"10.4230\/LIPIcs.FSTTCS.2024.23"},{"key":"e_1_3_2_1_18_1","unstructured":"Surendra Ghentiyala Zeyong Li and Noah Stephens-Davidowitz. 2025. Range Avoidance Arthur-Merlin and TFNP. 2025\/210\/. The full version of the present work"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Shafi Goldwasser and Michael Sipser. 1986. Private Coins versus Public Coins in Interactive Proof Systems. In STOC. https:\/\/doi.org\/10.1145\/12130.12137 10.1145\/12130.12137","DOI":"10.1145\/12130.12137"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami Xin Lyu and Xiuhan Wang. 2022. Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. In RANDOM. https:\/\/doi.org\/10.1145\/3718745 10.1145\/3718745","DOI":"10.1145\/3718745"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2026.52"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Shengtang Huang Xin Li and Yan Zhong. 2026. Range Avoidance and Remote Point: New Algorithms and Hardness. In ITCS. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2026.79 10.4230\/LIPIcs.ITCS.2026.79","DOI":"10.4230\/LIPIcs.ITCS.2026.79"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Rahul Ilango Jiatu Li and R. Ryan Williams. 2023. Indistinguishability Obfuscation Range Avoidance and Bounded Arithmetic. In STOC. https:\/\/doi.org\/10.1145\/3564246.3585187 10.1145\/3564246.3585187","DOI":"10.1145\/3564246.3585187"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Robert Kleinberg Oliver Korten Daniel Mitropolsky and Christos Papadimitriou. 2021. Total functions in the polynomial hierarchy. In ITCS. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2021.44 10.4230\/LIPIcs.ITCS.2021.44","DOI":"10.4230\/LIPIcs.ITCS.2021.44"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Adam R Klivans and Dieter van Melkebeek. 1999. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In STOC. https:\/\/doi.org\/10.1145\/301250.30142","DOI":"10.1145\/301250.30142"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Oliver Korten. 2021. The Hardest Explicit Construction. In FOCS. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00051 10.1109\/FOCS52979.2021.00051","DOI":"10.1109\/FOCS52979.2021.00051"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Oliver Korten. 2022. Derandomization from Time-Space Tradeoffs. In CCC. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2022.3 10.4230\/LIPIcs.CCC.2022.3","DOI":"10.4230\/LIPIcs.CCC.2022.3"},{"key":"e_1_3_2_1_29_1","volume-title":"Range Avoidance and the Complexity of Explicit Constructions. Bulletin of EATCS, 145, 1","author":"Korten Oliver","year":"2025","unstructured":"Oliver Korten. 2025. Range Avoidance and the Complexity of Explicit Constructions. Bulletin of EATCS, 145, 1 (2025)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Oliver Korten and Toniann Pitassi. 2024. Strong vs. Weak Range Avoidance and the Linear Ordering Principle. In FOCS. https:\/\/doi.org\/10.1109\/FOCS61266.2024.00089 10.1109\/FOCS61266.2024.00089","DOI":"10.1109\/FOCS61266.2024.00089"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","unstructured":"Oliver Korten Toniann Pitassi and Russell Impagliazzo. 2025. Stronger Cell Probe Lower Bounds via Local PRGs. In FOCS. https:\/\/doi.org\/10.1109\/FOCS63196.2025.00130 10.1109\/FOCS63196.2025.00130","DOI":"10.1109\/FOCS63196.2025.00130"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Oliver Korten and Rahul Santhanam. 2025. How to Construct Random Strings. In CCC. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2025.35 10.4230\/LIPIcs.CCC.2025.35","DOI":"10.4230\/LIPIcs.CCC.2025.35"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Neha Kuntewar and Jayalal Sarma. 2025. Avoiding Range via Turan-type Bounds. In RANDOM. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2025.62 10.4230\/LIPIcs.APPROX\/RANDOM.2025.62","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2025.62"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Zeyong Li. 2024. Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified Truly Uniform. In STOC. https:\/\/doi.org\/10.1145\/3618260.3649624 10.1145\/3618260.3649624","DOI":"10.1145\/3618260.3649624"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Zhenjian Lu Igor C. Oliveira Hanlin Ren and Rahul Santhanam. 2024. On the Complexity of Avoiding Heavy Elements. In FOCS. https:\/\/doi.org\/10.1109\/FOCS61266.2024.00140 10.1109\/FOCS61266.2024.00140","DOI":"10.1109\/FOCS61266.2024.00140"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Hanlin Ren Rahul Santhanam and Zhikun Wang. 2022. On the Range Avoidance Problem for Circuits. In FOCS. https:\/\/doi.org\/10.1109\/FOCS54457.2022.00067 10.1109\/FOCS54457.2022.00067","DOI":"10.1109\/FOCS54457.2022.00067"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Hanlin Ren Yichuan Wang and Yan Zhong. 2026. Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits. In ITCS. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2026.111 10.4230\/LIPIcs.ITCS.2026.111","DOI":"10.4230\/LIPIcs.ITCS.2026.111"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Ronen Shaltiel and Jad Silbak. 2024. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In STOC. https:\/\/doi.org\/10.1145\/3618260.3649735 10.1145\/3618260.3649735","DOI":"10.1145\/3618260.3649735"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800898","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:52Z","timestamp":1781028112000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":39,"alternative-id":["10.1145\/3798129.3800898","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800898","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}