{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:40Z","timestamp":1781031460950,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":81,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800842","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1326-1337","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Theory for Probabilistic Polynomial-Time Reasoning"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6084-4729","authenticated-orcid":false,"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, 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-4048-2385","authenticated-orcid":false,"given":"Igor C.","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2326-2233","authenticated-orcid":false,"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, 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":"crossref","first-page":"177","DOI":"10.4086\/toc.2011.v007a012","article-title":"On Circuit Lower Bounds from Derandomization","volume":"7","author":"Aaronson Scott","year":"2011","unstructured":"Scott Aaronson and Dieter van Melkebeek. 2011. On Circuit Lower Bounds from Derandomization. Theory Comput., 7, 1 (2011), 177\u2013184.","journal-title":"Theory Comput."},{"key":"e_1_3_2_1_2_1","volume-title":"Conference on Computational Complexity (CCC). IEEE","author":"Agrawal Manindra","year":"2001","unstructured":"Manindra Agrawal. 2001. Towards Uniform ^0-Isomorphisms. In Conference on Computational Complexity (CCC). IEEE, Chicago, IL, USA. 13\u201320."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-001-8191-1"},{"key":"e_1_3_2_1_4_1","first-page":"199","article-title":"Deterministic Simulation of Probabilistic Constant Depth","volume":"5","author":"Ajtai Mikl\u00f3s","year":"1989","unstructured":"Mikl\u00f3s Ajtai and Avi Wigderson. 1989. Deterministic Simulation of Probabilistic Constant Depth Circuits. Adv. Comput. Res., 5 (1989), 199\u2013222.","journal-title":"Circuits. Adv. Comput. Res."},{"key":"e_1_3_2_1_5_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge, UK. isbn:978-0-521-42426-4 http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264"},{"key":"e_1_3_2_1_6_1","volume-title":"The Proof Analysis Problem. In Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Arteche Noel","year":"2025","unstructured":"Noel Arteche, Albert Atserias, Susanna F. de Rezende, and Erfan Khaniki. 2025. The Proof Analysis Problem. In Symposium on Foundations of Computer Science (FOCS). IEEE, Sydney, Australia."},{"key":"e_1_3_2_1_7_1","volume-title":"On the Consistency of Circuit Lower Bounds for Non-deterministic Time. In Symposium on Theory of Computing (STOC). ACM","author":"Atserias Albert","year":"2023","unstructured":"Albert Atserias, Sam Buss, and Moritz M\u00fcller. 2023. On the Consistency of Circuit Lower Bounds for Non-deterministic Time. In Symposium on Theory of Computing (STOC). ACM, Orlando, FL, USA. 1257\u20131270."},{"key":"e_1_3_2_1_8_1","volume-title":"Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 1096\u20131107","author":"Atserias Albert","year":"2025","unstructured":"Albert Atserias and Iddo Tzameret. 2025. Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 1096\u20131107."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102796"},{"key":"e_1_3_2_1_10_1","unstructured":"Samuel R. Buss. 1986. Bounded Arithmetic. Bibliopolis Naples Italy. isbn:9788870881509 lccn:87134102"},{"key":"e_1_3_2_1_11_1","volume-title":"Logic of Computation","author":"Buss Samuel R.","unstructured":"Samuel R. Buss. 1997. Bounded Arithmetic and Propositional Proof Complexity. In Logic of Computation. Springer Berlin Heidelberg, Berlin, Germany. 67\u2013121. isbn:978-3-642-59048-1"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.37"},{"key":"e_1_3_2_1_13_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Carmosino Marco","unstructured":"Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, and Igor C. Oliveira. 2021. LEARN-uniform circuit lower bounds and provability in bounded arithmetic. In Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA."},{"key":"e_1_3_2_1_14_1","volume-title":"Provability of the Circuit Size Hierarchy and Its Consequences. In Innovations in Theoretical Computer Science Conference (ITCS). 325","author":"Carmosino Marco","year":"2025","unstructured":"Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira, and Dimitrios Tsintsilidas. 2025. Provability of the Circuit Size Hierarchy and Its Consequences. In Innovations in Theoretical Computer Science Conference (ITCS). 325, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, New York, NY, USA. 30:1\u201330:22."},{"key":"e_1_3_2_1_15_1","volume-title":"Reverse Mathematics of Complexity Lower Bounds. In Symposium on Foundations of Computer Science (FOCS). IEEE","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). IEEE, Chicago, IL, USA. 505\u2013527."},{"key":"e_1_3_2_1_16_1","volume-title":"Oliveira","author":"Chen Lijie","year":"2025","unstructured":"Lijie Chen, Jiatu Li, and Igor C. Oliveira. 2025. On the Unprovability of Circuit Size Bounds in Intuitionistic S^1_2. Log. Methods Comput. Sci., 21, 3 (2025)."},{"key":"e_1_3_2_1_17_1","volume-title":"Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 977\u2013985","author":"Chen Lijie","year":"2025","unstructured":"Lijie Chen, Ron D. Rothblum, and Roei Tell. 2025. Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 977\u2013985."},{"key":"e_1_3_2_1_18_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen and Roei Tell. 2021. Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. In Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA. 125\u2013136."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604943.3604950"},{"key":"e_1_3_2_1_20_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Chen Lijie","year":"2023","unstructured":"Lijie Chen, Roei Tell, and Ryan Williams. 2023. Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. In Symposium on Foundations of Computer Science (FOCS). IEEE, Orlando, FL, USA. 1008\u20131047."},{"key":"e_1_3_2_1_21_1","volume-title":"Symposium on Theory of Computing (STOC). ACM","author":"Chen Yilei","year":"2024","unstructured":"Yilei Chen and Jiatu Li. 2024. Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. In Symposium on Theory of Computing (STOC). ACM, Vancouver, BC, Canada. 620\u2013629."},{"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.2178\/jsl\/1203350791"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511676277"},{"key":"e_1_3_2_1_25_1","volume-title":"Comparing Notions of Full Derandomization. In Conference on Computational Complexity (CCC). IEEE","author":"Fortnow Lance","year":"2001","unstructured":"Lance Fortnow. 2001. Comparing Notions of Full Derandomization. In Conference on Computational Complexity (CCC). IEEE, Chicago, IL, USA. 28\u201334."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_27_1","unstructured":"Azza Gaysin. 2024. Proof complexity of universal algebra in a CSP dichotomy proof. arxiv:2403.06704. arxiv:2403.06704"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_20"},{"key":"e_1_3_2_1_29_1","volume-title":"Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 1341\u20131347","author":"Grosser Stefan","year":"2025","unstructured":"Stefan Grosser and Marco Carmosino. 2025. Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic. 1341\u20131347."},{"key":"e_1_3_2_1_30_1","volume-title":"Metamathematics of first-order arithmetic","author":"H\u00e1jek Petr","unstructured":"Petr H\u00e1jek and Pavel Pudl\u00e1k. 1993. Metamathematics of first-order arithmetic. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_1_31_1","volume-title":"Symposium on Theory of Computing (STOC). ACM","author":"Ilango Rahul","year":"2023","unstructured":"Rahul Ilango, Jiatu Li, and Ryan Williams. 2023. Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. In Symposium on Theory of Computing (STOC). ACM, Orlando, FL, USA. 1076\u20131089."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2005.06.008"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_35_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Jain Abhishek","year":"2022","unstructured":"Abhishek Jain and Zhengzhong Jin. 2022. Indistinguishability Obfuscation via Mathematical Proofs of Equivalence. In Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA. 1023\u20131034."},{"key":"e_1_3_2_1_36_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Jain Abhishek","year":"2025","unstructured":"Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, and Omer Paneth. 2025. On Succinct Obfuscation via Propositional Proofs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Sydney, Australia."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"e_1_3_2_1_38_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. Charles University in Prague."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200610019"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm017"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1245158087"},{"key":"e_1_3_2_1_43_1","article-title":"Elementary analytic functions in VTC^0","volume":"174","author":"Je\u0159\u00e1bek Emil","year":"2023","unstructured":"Emil Je\u0159\u00e1bek. 2023. Elementary analytic functions in VTC^0. Annals of Pure and Applied Logic, 174, 6 (2023), Article no. 103269, 50 pp","journal-title":"Annals of Pure and Applied Logic"},{"key":"e_1_3_2_1_44_1","volume-title":"Symposium on Theory of Computing (STOC). ACM","author":"Jin Zhengzhong","year":"2024","unstructured":"Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Vinod Vaikuntanathan. 2024. SNARGs under LWE via Propositional Proofs. In Symposium on Theory of Computing (STOC). ACM, Vancouver, BC, Canada. 1750\u20131757."},{"key":"e_1_3_2_1_45_1","volume-title":"Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic.","author":"Jin Zhengzhong","year":"2025","unstructured":"Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan. 2025. Universal SNARGs for NP from Proofs of Correctness. In Symposium on Theory of Computing (STOC). ACM, Prague, Czech Republic."},{"key":"e_1_3_2_1_46_1","volume-title":"Interactive Proofs and Proof Complexity Generators. In Symposium on Foundations of Computer Science, (FOCS). IEEE","author":"Khaniki Erfan","year":"2024","unstructured":"Erfan Khaniki. 2024. Jump Operators, Interactive Proofs and Proof Complexity Generators. In Symposium on Foundations of Computer Science, (FOCS). IEEE, Chicago, IL, USA. 573\u2013593."},{"key":"e_1_3_2_1_47_1","first-page":"1","article-title":"Total Functions in the Polynomial Hierarchy. In Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik","volume":"44","author":"Kleinberg Robert","year":"2021","unstructured":"Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. 2021. Total Functions in the Polynomial Hierarchy. In Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Virtual Event. 44:1\u201344:18.","journal-title":"Virtual Event."},{"key":"e_1_3_2_1_48_1","volume-title":"The Hardest Explicit Construction. In Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Korten Oliver","year":"2021","unstructured":"Oliver Korten. 2021. The Hardest Explicit Construction. In Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA. 433\u2013444."},{"key":"e_1_3_2_1_49_1","volume-title":"Computational Complexity Conference (CCC). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik","author":"Korten Oliver","year":"2022","unstructured":"Oliver Korten. 2022. Derandomization from Time-Space Tradeoffs. In Computational Complexity Conference (CCC). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Philadelphia, PA, USA. 37:1\u201337:26."},{"key":"e_1_3_2_1_50_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_51_1","volume-title":"Propositional Logic, and Complexity Theory","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 1995. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, Berlin, Germany. isbn:978-0-521-45205-2"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_54_1","volume-title":"Proof Complexity Generators","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 2025. Proof Complexity Generators. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(3:5)2012"},{"key":"e_1_3_2_1_56_1","volume-title":"TR25-086","author":"Jiatu Li.","year":"2025","unstructured":"Jiatu Li. 2025. An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists. Electron. Colloquium Comput. Complex., TR25-086 (2025)."},{"key":"e_1_3_2_1_57_1","unstructured":"Jiawei Li Yuhao Li and Hanlin Ren. 2024. Meta-Mathematics of Resolution Lower Bounds: A TFNP Perspective. Preprint."},{"key":"e_1_3_2_1_58_1","volume-title":"Symposium on Theory of Computing (STOC). ACM","author":"Li Jiatu","unstructured":"Jiatu Li and Igor C. Oliveira. 2023. Unprovability of strong complexity lower bounds in bounded arithmetic. In Symposium on Theory of Computing (STOC). ACM, Orlando, FL, USA. 1051\u20131057."},{"key":"e_1_3_2_1_59_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Li Jiatu","year":"2024","unstructured":"Jiatu Li, Edward Pyne, and Roei Tell. 2024. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. In Symposium on Foundations of Computer Science (FOCS). IEEE, Chicago, IL, USA. 1\u201313."},{"key":"e_1_3_2_1_60_1","volume-title":"Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. In Computational Complexity Conference (CCC). 234","author":"Liu Yanyi","year":"2022","unstructured":"Yanyi Liu and Rafael Pass. 2022. Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. In Computational Complexity Conference (CCC). 234, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Philadelphia, PA, USA. 35:1\u201335:17."},{"key":"e_1_3_2_1_61_1","volume-title":"Bounded Arithmetic and Formalizing Probabilistic Proofs. Ph. D. Dissertation","author":"Man L\u00ea Dai Tri","year":"1807","unstructured":"Dai Tri Man L\u00ea. 2014. 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_62_1","volume-title":"International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Springer","author":"Ma Yaohua","year":"2025","unstructured":"Yaohua Ma, Chenxin Dai, and Elaine Shi. 2025. Quasi-Linear Indistinguishability Obfuscation via Mathematical Proofs of Equivalence and Applications. In International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Springer, Madrid, Spain. 157\u2013186."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_66_1","volume-title":"Combinatorics in Bounded Arithmetic. Ph. D. Dissertation","author":"Ojakian Kerry","unstructured":"Kerry Ojakian. 2004. Combinatorics in Bounded Arithmetic. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3726856.3726862"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028061"},{"key":"e_1_3_2_1_69_1","volume-title":"Complexity Theory in Feasible Mathematics. Ph. D. Dissertation","author":"Pich J\u00e1n","unstructured":"J\u00e1n Pich. 2014. Complexity Theory in Feasible Mathematics. Ph. D. Dissertation. Charles University in Prague."},{"key":"e_1_3_2_1_70_1","volume-title":"Symposium on Theory of Computing (STOC). ACM","author":"Pich J\u00e1n","year":"2021","unstructured":"J\u00e1n Pich and Rahul Santhanam. 2021. Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. In Symposium on Theory of Computing (STOC). ACM, Virtual Event, Italy. 223\u2013233."},{"key":"e_1_3_2_1_71_1","volume-title":"Computer Science Logic (CSL) (Lecture Notes in Computer Science","volume":"317","author":"Pudl\u00e1k Pavel","year":"1990","unstructured":"Pavel Pudl\u00e1k. 1990. Ramsey\u2019s Theorem in Bounded Arithmetic. In Computer Science Logic (CSL) (Lecture Notes in Computer Science, Vol. 533). Springer, Heidelberg, Germany. 308\u2013317."},{"key":"e_1_3_2_1_72_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. Birkh\u00e4user, Berlin, Germany. 344\u2013386."},{"key":"e_1_3_2_1_73_1","volume-title":"On the Range Avoidance Problem for Circuits. In Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Ren Hanlin","year":"2022","unstructured":"Hanlin Ren, Rahul Santhanam, and Zhikun Wang. 2022. On the Range Avoidance Problem for Circuits. In Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA."},{"key":"e_1_3_2_1_74_1","volume-title":"Clote and J. Kraj\u00ed\u010dek (Eds.) (Oxford Logic Guides","volume":"319","author":"Riis S\u00f8ren M.","year":"1993","unstructured":"S\u00f8ren M. Riis. 1993. Making infinite structures finite in models of second order bounded arithmetic. In Arithmetic, Proof Theory, and Computational Complexity, P. Clote and J. Kraj\u00ed\u010dek (Eds.) (Oxford Logic Guides, Vol. 23). Oxford University Press, Oxford. 289\u2013319."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2019.105841"},{"key":"e_1_3_2_1_76_1","volume-title":"The weak pigeonhole principle in models of bounded arithmetic. Ph. D. Dissertation","author":"Thapen Neil","unstructured":"Neil Thapen. 2002. The weak pigeonhole principle in models of bounded arithmetic. Ph. D. Dissertation. University of Oxford."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2412.09984"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2504.03320"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_1_81_1","volume-title":"Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Chi-Chih Yao Andrew","year":"1982","unstructured":"Andrew Chi-Chih Yao. 1982. Theory and Applications of Trapdoor Functions (Extended Abstract). In Symposium on Foundations of Computer Science (FOCS). IEEE, Chicago, IL, USA. 80\u201391."}],"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.3800842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:30Z","timestamp":1781028270000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":81,"alternative-id":["10.1145\/3798129.3800842","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800842","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"}}]}}