{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:33Z","timestamp":1781031453250,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":100,"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":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CAREER 1942789"],"award-info":[{"award-number":["CAREER 1942789"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF 2420092"],"award-info":[{"award-number":["CCF 2420092"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007880","name":"Johns Hopkins University","doi-asserted-by":"publisher","award":["Catalyst award"],"award-info":[{"award-number":["Catalyst award"]}],"id":[{"id":"10.13039\/100007880","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JP Morgan","award":["Faculty Award"],"award-info":[{"award-number":["Faculty Award"]}]},{"name":"Jane Street","award":["Graduate Research Fellowship"],"award-info":[{"award-number":["Graduate Research Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800724","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"31-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5244-7222","authenticated-orcid":false,"given":"Yao-Ching","family":"Hsieh","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3572-7643","authenticated-orcid":false,"given":"Abhishek","family":"Jain","sequence":"additional","affiliation":[{"name":"NTT Research, Sunnyvale, USA"},{"name":"Johns Hopkins University, Baltimore, USA"}],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4904-3637","authenticated-orcid":false,"given":"Surya","family":"Mathialagan","sequence":"additional","affiliation":[{"name":"NTT Research, Sunnyvale, 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","DOI":"10.1145\/3564246.3585253"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718276"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188924"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-016-9241-9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_9"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055497"},{"key":"e_1_3_2_1_10_1","volume-title":"Bounded arithmetic","author":"Buss Samuel R","unstructured":"Samuel R Buss. 1985. Bounded arithmetic. Princeton University."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/JSL.2013.37"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-16(2:12)2020"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00153-019-00681-Y"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"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.4230\/LIPICS.ITCS.2025.30"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Liyan Chen and Zhengzhong Jin. 2025. On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting). In FOCS (to appear).","DOI":"10.1109\/FOCS63196.2025.00092"},{"key":"e_1_3_2_1_19_1","volume-title":"Reverse Mathematics of Complexity Lower Bounds. In Symposium on Foundations of Computer Science (FOCS). 505\u2013527","author":"Chen Lijie","unstructured":"Lijie Chen, Jiatu Li, and Igor C. Oliveira. 2024. Reverse Mathematics of Complexity Lower Bounds. In Symposium on Foundations of Computer Science (FOCS). 505\u2013527."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-21(3:26)2025"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718177"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38551-3_20"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84259-8_14"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00016"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1073\/pnas.50.6.1143","article-title":"The independence of the continuum hypothesis","volume":"50","author":"Cohen Paul J","year":"1963","unstructured":"Paul J Cohen. 1963. The independence of the continuum hypothesis. Proceedings of the National Academy of Sciences, 50, 6 (1963), 1143\u20131148.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.51.1.105"},{"key":"e_1_3_2_1_27_1","volume-title":"Logical foundations of proof complexity. 31","author":"Cook Stephen","unstructured":"Stephen Cook and Phuong Nguyen. 2010. Logical foundations of proof complexity. 31, Cambridge University Press Cambridge."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803756"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2178\/JSL\/1203350791"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90141-J"},{"key":"e_1_3_2_1_31_1","volume-title":"The relative efficiency of propositional proof systems. The journal of symbolic logic, 44, 1","author":"Cook Stephen A","year":"1979","unstructured":"Stephen A Cook and Robert A Reckhow. 1979. The relative efficiency of propositional proof systems. The journal of symbolic logic, 44, 1 (1979), 36\u201350."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90044-E"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00103"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488667"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_2_1_37_1","volume-title":"\u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I. Monatshefte f\u00fcr mathematik und physik, 38, 1","author":"G\u00f6del Kurt","year":"1931","unstructured":"Kurt G\u00f6del. 1931. \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I. Monatshefte f\u00fcr mathematik und physik, 38, 1 (1931), 173\u2013198."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718216"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07085-3_18"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Rahul Ilango. 2025. G\u00f6del in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction No Setup and Perfect Soundness. In FOCS (to appear).","DOI":"10.1109\/FOCS63196.2025.00058"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585187"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00100"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01881-6_13"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Abhishek Jain Zhengzhong Jin Surya Mathialagan and Omer Paneth. 2025. On Succinct Obfuscation via Propositional Proofs (or: How to use pv-IO). STOC (to appear).","DOI":"10.1109\/FOCS63196.2025.00091"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451093"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_2_1_49_1","volume-title":"Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation","author":"Je\u0159\u00e1bek Emil","unstructured":"Emil Je\u0159\u00e1bek. 2005. Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation. Faculty of Mathematics and Physics, Charles University. Prague."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649770"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718104"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585200"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30617-4_16"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_4"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316411"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591809"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90459-3_12"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_61_1","volume-title":"Range Avoidance and the Complexity of Explicit Constructions. Bull. EATCS, 145","author":"Korten Oliver","year":"2025","unstructured":"Oliver Korten. 2025. Range Avoidance and the Complexity of Explicit Constructions. Bull. EATCS, 145 (2025), http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/825"},{"key":"e_1_3_2_1_62_1","volume-title":"Bounded arithmetic, propositional logic and complexity theory. 60","author":"Krajicek Jan","unstructured":"Jan Krajicek. 1995. Bounded arithmetic, propositional logic and complexity theory. 60, Cambridge University Press."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_3_2_1_64_1","volume-title":"Forcing with Random Variables and Proof Complexity","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 2011. Forcing with Random Variables and Proof Complexity (London Mathematical Society lecture note series, Vol. 382). Cambridge University Press. isbn:978-0-521-15433-8 http:\/\/www.cambridge.org\/de\/academic\/subjects\/mathematics\/logic-categories-and-sets\/forcing-random-variables-and-proof-complexity?format=PB"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061311000979"},{"key":"e_1_3_2_1_66_1","volume-title":"Proof complexity. 170","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof complexity. 170, Cambridge University Press."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1017\/bsl.2023.40","article-title":"On the existence of strong proof complexity generators","volume":"30","author":"Kraj\u00ed\u010dek Jan","year":"2024","unstructured":"Jan Kraj\u00ed\u010dek. 2024. On the existence of strong proof complexity generators. Bulletin of Symbolic Logic, 30, 1 (2024), 20\u201340.","journal-title":"Bulletin of Symbolic Logic"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-13(1:4)2017"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2674"},{"key":"e_1_3_2_1_71_1","volume-title":"Proof Complexity Generators","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 2025. Proof Complexity Generators. Cambridge University Press."},{"key":"e_1_3_2_1_72_1","volume-title":"Bounded Arithmetic and Formalizing Probabilistic Proofs. Ph. D. Dissertation","author":"Man Le Dai Tri","year":"1807","unstructured":"Dai Tri Man Le. 2019. Bounded Arithmetic and Formalizing Probabilistic Proofs. Ph. D. Dissertation. University of Toronto, Canada. http:\/\/hdl.handle.net\/1807\/94486"},{"key":"e_1_3_2_1_73_1","volume-title":"TR24-190","author":"Li Jiawei","year":"2024","unstructured":"Jiawei Li, Yuhao Li, and Hanlin Ren. 2024. Metamathematics of Resolution Lower Bounds: A TFNP Perspective. Electron. Colloquium Comput. Complex., TR24-190 (2024), ECCC:TR24-190. https:\/\/eccc.weizmann.ac.il\/report\/2024\/190"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585144"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451121"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91131-6_6"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2019.102735"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78017-2_14"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_82_1","volume-title":"Combinatorics in bounded arithmetic","author":"Ojakian Kerry","unstructured":"Kerry Ojakian. 2004. Combinatorics in bounded arithmetic. Carnegie Mellon University."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3726856.3726862"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028061"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2014.08.004"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(2:8)2015"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451117"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78023-3_1"},{"key":"e_1_3_2_1_90_1","volume-title":"Bounded arithmetic and lower bounds in Boolean complexity","author":"Razborov Alexander A","unstructured":"Alexander A Razborov. 1995. Bounded arithmetic and lower bounds in Boolean complexity. In Feasible Mathematics II. Springer, 344\u2013386."},{"key":"e_1_3_2_1_91_1","volume-title":"Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: mathematics, 59, 1","author":"Razborov Alexander A","year":"1995","unstructured":"Alexander A Razborov. 1995. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: mathematics, 59, 1 (1995), 205."},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"e_1_3_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591825"},{"key":"e_1_3_2_1_94_1","volume-title":"Axiomatic set theory","author":"Suppes Patrick","unstructured":"Patrick Suppes. 1972. Axiomatic set theory. Courier Corporation."},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2005.04.005"},{"key":"e_1_3_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15979-4_15"},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649671"},{"key":"e_1_3_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01907-3_10"},{"key":"e_1_3_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68403-6_3"},{"key":"e_1_3_2_1_100_1","volume-title":"Some problems in logic and number theory and their connections. Ph. D. Thesis","author":"Woods Alan","unstructured":"Alan Woods. 1981. Some problems in logic and number theory and their connections. Ph. D. Thesis, Univ. of Manchester."}],"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.3800724","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:10Z","timestamp":1781028250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":100,"alternative-id":["10.1145\/3798129.3800724","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800724","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"}}]}}