{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:41:06Z","timestamp":1787496066179,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","award":["URF\\R1\\191059"],"award-info":[{"award-number":["URF\\R1\\191059"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451085","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"303-316","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Pseudodeterministic algorithms and the structure of probabilistic time"],"prefix":"10.1145","author":[{"given":"Zhenjian","family":"Lu","sequence":"first","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Igor C.","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"781","article-title":"PRIMES is","volume":"2","author":"Agrawal M.","year":"2002","unstructured":"M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Ann. of Math., 2:781\u2013793, 2002.","journal-title":"P. Ann. of Math."},{"key":"e_1_3_2_1_2_1","volume-title":"Springer","author":"Allender E.","year":"1992","unstructured":"E. Allender. Applications of time-bounded Kolmogorov complexity in complexity theory. In Kolmogorov complexity and computational complexity, pages 4\u201322. Springer, 1992."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45294-X_1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_2_1_5_1","first-page":"208","volume-title":"RANDOM","author":"Barak B.","year":"2002","unstructured":"B. Barak. A probabilistic-time hierarchy theorem for \"slightly non-uniform\" algorithms. In RANDOM, pages 194\u2013208, 2002."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00079"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80028-5"},{"key":"e_1_3_2_1_8_1","volume-title":"ITCS","author":"Dixon P.","year":"2021","unstructured":"P. Dixon, A. Pavan, and N. V. Vinodchandran. Complete problems for multi-pseudodeterministic computations. In ITCS, 2021."},{"key":"e_1_3_2_1_9_1","first-page":"11","volume-title":"MFCS","author":"Dixon P.","year":"2018","unstructured":"P. Dixon, A. Pavan, and N. V. Vinodchandran. On pseudodeterministic approximation algorithms. In MFCS, pages 61:1\u201361:11, 2018."},{"key":"e_1_3_2_1_10_1","volume-title":"Manuscript","author":"Dixon P.","year":"2021","unstructured":"P. Dixon, A. Pavan, and V. Vinodchandran. Promise problems meet pseudodeterminism. Manuscript, 2021."},{"key":"e_1_3_2_1_11_1","volume-title":"Kolmogorov complexity and computational complexity. Complexity of Computations and Proofs. Quaderni di Matematica, 13","author":"Fortnow L.","year":"2004","unstructured":"L. Fortnow. Kolmogorov complexity and computational complexity. Complexity of Computations and Proofs. Quaderni di Matematica, 13, 2004."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.33"},{"key":"e_1_3_2_1_13_1","first-page":"136","article-title":"Probabilistic search algorithms with unique answers and their cryptographic applications","volume":"18","author":"Gat E.","year":"2011","unstructured":"E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electron. Colloquium Comput. Complex., 18:136, 2011.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_14_1","first-page":"135","article-title":"Doubly-efficient pseudo-deterministic proofs","volume":"26","author":"Goemans M. X.","year":"2019","unstructured":"M. X. Goemans, S. Goldwasser, and D. Holden. Doubly-efficient pseudo-deterministic proofs. Electron. Colloquium Comput. Complex., 26:135, 2019.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_15_1","first-page":"12","article-title":"Multi-pseudodeterministic algorithms","volume":"26","author":"Goldreich O.","year":"2019","unstructured":"O. Goldreich. Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex., 26:12, 2019.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422453"},{"key":"e_1_3_2_1_17_1","first-page":"208","article-title":"Perfect bipartite matching in pseudo-deterministic RNC","volume":"22","author":"Goldwasser S.","year":"2015","unstructured":"S. Goldwasser and O. Grossman. Perfect bipartite matching in pseudo-deterministic RNC. Electron. Colloquium Comput. Complex., 22:208, 2015.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_18_1","first-page":"18","volume-title":"ITCS","author":"Goldwasser S.","year":"2018","unstructured":"S. Goldwasser, O. Grossman, and D. Holden. Pseudo-deterministic proofs. In ITCS, pages 17:1\u201317:18, 2018."},{"key":"e_1_3_2_1_19_1","first-page":"25","volume-title":"ITCS","author":"Goldwasser S.","year":"2020","unstructured":"S. Goldwasser, O. Grossman, S. Mohanty, and D. P. Woodruff. Pseudo-deterministic streaming. In ITCS, pages 79:1\u201379:25, 2020."},{"key":"e_1_3_2_1_20_1","first-page":"207","article-title":"Finding primitive roots pseudo-deterministically","volume":"22","author":"Grossman O.","year":"2015","unstructured":"O. Grossman. Finding primitive roots pseudo-deterministically. Electron. Colloquium Comput. Complex., 22:207, 2015.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.38"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321362"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384251"},{"key":"e_1_3_2_1_24_1","volume-title":"A note on unconditional subexponential-time pseudo-deterministic algorithms for BPP search problems. CoRR, abs\/1707.05808","author":"Holden D.","year":"2017","unstructured":"D. Holden. A note on unconditional subexponential-time pseudo-deterministic algorithms for BPP search problems. CoRR, abs\/1707.05808, 2017."},{"key":"e_1_3_2_1_25_1","first-page":"229","volume-title":"STOC","author":"Impagliazzo R.","unstructured":"R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220\u2013229. ACM, 1997."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90057-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90037-X"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80060-1"},{"key":"e_1_3_2_1_30_1","volume-title":"Pseudodeterministic algorithms and the structure of probabilistic time. CoRR, abs\/2103.08539","author":"Lu Z.","year":"2021","unstructured":"Z. Lu, I. C. Oliveira, and R. Santhanam. Pseudodeterministic algorithms and the structure of probabilistic time. CoRR, abs\/2103.08539, 2021."},{"key":"e_1_3_2_1_31_1","first-page":"14","volume-title":"ICALP","author":"Oliveira I. C.","year":"2019","unstructured":"I. C. Oliveira. Randomness and intractability in Kolmogorov complexity. In ICALP, pages 32:1\u201332:14, 2019."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055500"},{"key":"e_1_3_2_1_33_1","first-page":"19","volume-title":"RANDOM","author":"Oliveira I. C.","year":"2018","unstructured":"I. C. Oliveira and R. Santhanam. Pseudo-derandomizing learning and approximation. In RANDOM, pages 55:1\u201355:19, 2018."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322061"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1965.11"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02542-1"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90015-4"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451085","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:53Z","timestamp":1750181093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":39,"alternative-id":["10.1145\/3406325.3451085","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451085","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}