{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T16:47:19Z","timestamp":1776962839406,"version":"3.51.4"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    A randomized algorithm for a search problem is\n                    <jats:italic toggle=\"yes\">pseudodeterministic<\/jats:italic>\n                    if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [\n                    <jats:xref ref-type=\"bibr\">16<\/jats:xref>\n                    ] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.\n                  <\/jats:p>\n                  <jats:p>\n                    We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an\n                    <jats:italic toggle=\"yes\">unconditional<\/jats:italic>\n                    polynomial-time randomized algorithm\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    such that, for infinitely many values of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ,\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(B(1^n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    outputs a canonical\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -bit prime\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(p_n\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    with high probability. More generally, we prove that for every dense property\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    . This improves upon a subexponential-time construction of Oliveira and Santhanam [\n                    <jats:xref ref-type=\"bibr\">49<\/jats:xref>\n                    ].\n                  <\/jats:p>\n                  <jats:p>\n                    Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [\n                    <jats:xref ref-type=\"bibr\">11<\/jats:xref>\n                    ], using a variant of the Shaltiel\u2013Umans generator [\n                    <jats:xref ref-type=\"bibr\">51<\/jats:xref>\n                    ].\n                  <\/jats:p>","DOI":"10.1145\/3803408","type":"journal-article","created":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T20:56:23Z","timestamp":1773953783000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Pseudodeterministic Construction of Primes"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6084-4729","authenticated-orcid":false,"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"UC Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3990-4751","authenticated-orcid":false,"given":"Zhenjian","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford","place":["Oxford, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4048-2385","authenticated-orcid":false,"given":"Igor","family":"Oliveira","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7632-7574","authenticated-orcid":false,"given":"Hanlin","family":"Ren","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford","place":["Oxford, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8716-6091","authenticated-orcid":false,"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford","place":["Oxford, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/83.3.532"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98113-0_16"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.30"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-31371-4_22"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520043"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649624"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00048"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00021"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.4064\/aa-2-1-23-46","article-title":"On the order of magnitude of the difference between consecutive prime numbers","volume":"2","author":"Cram\u00e9r Harald","year":"1936","unstructured":"Harald Cram\u00e9r. 1936. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2 (1936), 23\u201346. Retrieved from http:\/\/eudml.org\/doc\/205441","journal-title":"Acta Arithmetica"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2018.61"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.66"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520043"},{"key":"e_1_3_2_17_2","first-page":"136","article-title":"Probabilistic search algorithms with unique answers and their cryptographic applications","volume":"18","author":"Gat Eran","year":"2011","unstructured":"Eran Gat and Shafi Goldwasser. 2011. Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC) 18 (2011), 136. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2011\/136\/","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.41"},{"key":"e_1_3_2_20_2","first-page":"135","article-title":"Doubly-efficient pseudo-deterministic proofs","volume":"26","author":"Goemans Michel X.","year":"2019","unstructured":"Michel X. Goemans, Shafi Goldwasser, and Dhiraj Holden. 2019. Doubly-efficient pseudo-deterministic proofs. Electronic Colloquium on Computational Complexity (ECCC) 26 (2019), 135. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2019\/135","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_2_22_2","first-page":"101","article-title":"On the doubly-efficient interactive proof systems of GKR","volume":"24","author":"Goldreich Oded","year":"2017","unstructured":"Oded Goldreich. 2017. On the doubly-efficient interactive proof systems of GKR. Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 101. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2017\/101","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000084"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-88946-2_2"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422453"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.87"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.17"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.79"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.36"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_32_2","first-page":"207","article-title":"Finding primitive roots pseudo-deterministically","volume":"22","author":"Grossman Ofer","year":"2015","unstructured":"Ofer Grossman. 2015. Finding primitive roots pseudo-deterministically. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 207. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2015\/207","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.38"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_55"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814590"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90037-X"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519976"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649615"},{"key":"e_1_3_2_45_2","article-title":"Theory and applications of probabilistic kolmogorov complexity","volume":"137","author":"Lu Zhenjian","year":"2022","unstructured":"Zhenjian Lu and Igor C. Oliveira. 2022. Theory and applications of probabilistic kolmogorov complexity. Bull. EATCS 137 (2022). Retrieved from http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/700","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451085"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/3-540-48686-0_21","volume-title":"International Computing and Combinatorics Conference (COCOON)","author":"Miltersen Peter Bro","year":"1999","unstructured":"Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. 1999. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In International Computing and Combinatorics Conference (COCOON). 210\u2013220. DOI:10.1007\/3-540-48686-0_21"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.32"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055500"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.55"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1992-1106981-9"},{"key":"e_1_3_2_54_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-60615-7","volume-title":"Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems","author":"Sudan Madhu","year":"1995","unstructured":"Madhu Sudan. 1995. Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems. Lecture Notes in Computer Science, Vol. 1001. Springer. DOI:10.1007\/3-540-60615-7"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02542-1"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3"},{"key":"e_1_3_2_60_2","article-title":"The geometry of rounding","volume":"22","author":"Woude Jason Vander","year":"2022","unstructured":"Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran. 2022. The geometry of rounding. Electronic Colloquium on Computational Complexity (ECCC) TR22-160 (2022). Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2022\/160","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3803408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T16:11:53Z","timestamp":1776960713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3803408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3803408"],"URL":"https:\/\/doi.org\/10.1145\/3803408","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2024-04-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}