{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:06:04Z","timestamp":1787504764042,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055500","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T16:27:45Z","timestamp":1497544065000},"page":"665-677","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Pseudodeterministic constructions in subexponential time"],"prefix":"10.1145","author":[{"given":"Igor C.","family":"Oliveira","sequence":"first","affiliation":[{"name":"Charles University in Prague, Czechia"}],"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":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"781","article-title":"PRIMES is in P","volume":"2","author":"Agrawal Manindra","year":"2002","unstructured":"Manindra Agrawal , Neeraj Kayal , and Nitin Saxena . 2002 . PRIMES is in P . Ann. of Math. 2 (2002), 781 \u2013 793 . Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. 2002. PRIMES is in P. Ann. of Math. 2 (2002), 781\u2013793.","journal-title":"Ann. of Math."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1725"},{"key":"e_1_3_2_2_3_1","unstructured":"Sanjeev Arora and Boaz Barak. 2009.  Sanjeev Arora and Boaz Barak. 2009."},{"key":"e_1_3_2_2_4_1","volume-title":"A Modern Approach","author":"Theory Complexity","unstructured":"Complexity Theory : A Modern Approach . Cambridge University Press . Complexity Theory: A Modern Approach. Cambridge University Press."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_2_6_1","unstructured":"Roger Baker Glyn Harman and Janos Pintz. 2001.  Roger Baker Glyn Harman and Janos Pintz. 2001."},{"key":"e_1_3_2_2_7_1","volume-title":"II. Proceedings of the London Mathematical Society 83","author":"The","year":"2001","unstructured":"The difference between consecutive primes , II. Proceedings of the London Mathematical Society 83 , 3 ( 2001 ), 532\u2013562. The difference between consecutive primes, II. Proceedings of the London Mathematical Society 83, 3 (2001), 532\u2013562."},{"key":"e_1_3_2_2_8_1","unstructured":"Boaz Barak. 2002.  Boaz Barak. 2002."},{"key":"e_1_3_2_2_9_1","volume-title":"International Workshop on Randomization and Approximation Techniques (RANDOM). 194\u2013208","author":"A","unstructured":"A probabilistic-time hierarchy theorem for \u201cslightly nonuniform\u201d algorithms . In International Workshop on Randomization and Approximation Techniques (RANDOM). 194\u2013208 . A probabilistic-time hierarchy theorem for \u201cslightly nonuniform\u201d algorithms. In International Workshop on Randomization and Approximation Techniques (RANDOM). 194\u2013208."},{"key":"e_1_3_2_2_10_1","unstructured":"Eshan Chattopadhyay and David Zuckerman. 2016.  Eshan Chattopadhyay and David Zuckerman. 2016."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897528"},{"key":"e_1_3_2_2_12_1","unstructured":"Gil Cohen. 2016.  Gil Cohen. 2016."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897530"},{"key":"e_1_3_2_2_14_1","volume-title":"Conference on Computational Complexity (CCC). 28\u201334","author":"Fortnow Lance","year":"2001","unstructured":"Lance Fortnow . 2001 . Comparing notions of full derandomization . In Conference on Computational Complexity (CCC). 28\u201334 . DOI:https:\/\/ Lance Fortnow. 2001. Comparing notions of full derandomization. In Conference on Computational Complexity (CCC). 28\u201334. DOI:https:\/\/"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.33"},{"key":"e_1_3_2_2_16_1","unstructured":"Eran Gat and Shafi Goldwasser. 2011.  Eran Gat and Shafi Goldwasser. 2011."},{"key":"e_1_3_2_2_17_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 18","author":"Probabilistic","year":"2011","unstructured":"Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC) 18 ( 2011 ), 136. http:\/\/eccc.hpi-web.de\/report\/ 2011\/136 Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC) 18 (2011), 136. http:\/\/eccc.hpi-web.de\/report\/ 2011\/136"},{"key":"e_1_3_2_2_18_1","unstructured":"Oded Goldreich. 2008.  Oded Goldreich. 2008."},{"key":"e_1_3_2_2_19_1","unstructured":"Computational Complexity - A Conceptual Perspective. Cambridge University Press.   Computational Complexity - A Conceptual Perspective. Cambridge University Press."},{"key":"e_1_3_2_2_20_1","unstructured":"Oded Goldreich. 2011.  Oded Goldreich. 2011."},{"key":"e_1_3_2_2_21_1","unstructured":"In a world of P = BPP. In Studies in Complexity and Cryptography. 191\u2013232. DOI:https:\/\/  In a world of P = BPP. In Studies in Complexity and Cryptography. 191\u2013232. DOI:https:\/\/"},{"key":"e_1_3_2_2_22_1","unstructured":"Oded Goldreich Shafi Goldwasser and Dana Ron. 2013.  Oded Goldreich Shafi Goldwasser and Dana Ron. 2013."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422453"},{"key":"e_1_3_2_2_24_1","first-page":"208","article-title":"Perfect bipartite matching in pseudodeterministic RNC","volume":"22","author":"Goldwasser Shafi","year":"2015","unstructured":"Shafi Goldwasser and Ofer Grossman . 2015 . Perfect bipartite matching in pseudodeterministic RNC . Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 208 . http:\/\/eccc.hpiweb.de\/report\/2015\/208 Shafi Goldwasser and Ofer Grossman. 2015. Perfect bipartite matching in pseudodeterministic RNC. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 208. http:\/\/eccc.hpiweb.de\/report\/2015\/208","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_25_1","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 . http:\/\/eccc. hpiweb.de\/report\/2015\/207 Ofer Grossman. 2015. Finding primitive roots pseudo-deterministically. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 207. http:\/\/eccc. hpiweb.de\/report\/2015\/207","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_26_1","unstructured":"Russell Impagliazzo. 1995.  Russell Impagliazzo. 1995."},{"key":"e_1_3_2_2_27_1","volume-title":"Structure in Complexity Theory Conference (CCC). 134\u2013147","author":"A","unstructured":"A personal view of average-case complexity . In Structure in Complexity Theory Conference (CCC). 134\u2013147 . A personal view of average-case complexity. In Structure in Complexity Theory Conference (CCC). 134\u2013147."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_2_2_31_1","unstructured":"Stasys Jukna. 2012.  Stasys Jukna. 2012."},{"key":"e_1_3_2_2_32_1","unstructured":"Boolean Function Complexity - Advances and Frontiers. Springer.   Boolean Function Complexity - Advances and Frontiers. Springer."},{"key":"e_1_3_2_2_33_1","unstructured":"Valentine Kabanets. 2001.  Valentine Kabanets. 2001."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"key":"e_1_3_2_2_35_1","volume-title":"Odlyzko","author":"Lagarias Jeffrey C.","year":"1987","unstructured":"Jeffrey C. Lagarias and Andrew M . Odlyzko . 1987 . Jeffrey C. Lagarias and Andrew M. Odlyzko. 1987."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90037-X"},{"key":"e_1_3_2_2_37_1","volume-title":"Oliveira and Rahul Santhanam","author":"Igor","year":"2016","unstructured":"Igor C. Oliveira and Rahul Santhanam . 2016 . Igor C. Oliveira and Rahul Santhanam. 2016."},{"key":"e_1_3_2_2_38_1","volume-title":"Circuit Lower Bounds and Pseudorandomness. Available on arXiv:cs.CC\/1611.01190","author":"Learning Algorithms Conspiracies","year":"2016","unstructured":"Conspiracies between Learning Algorithms , Circuit Lower Bounds and Pseudorandomness. Available on arXiv:cs.CC\/1611.01190 ( 2016 ). Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. Available on arXiv:cs.CC\/1611.01190 (2016)."},{"key":"e_1_3_2_2_39_1","volume-title":"Oliveira and Rahul Santhanam","author":"Igor","year":"2016","unstructured":"Igor C. Oliveira and Rahul Santhanam . 2016 . Pseudodeterministic constructions in subexponential time. Available on arXiv:cs.CC\/1612.01817 (2016). Igor C. Oliveira and Rahul Santhanam. 2016. Pseudodeterministic constructions in subexponential time. Available on arXiv:cs.CC\/1612.01817 (2016)."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9368-x"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02542-1"},{"key":"e_1_3_2_2_43_1","volume-title":"International Congress of Mathematicians.","author":"Trevisan Luca","year":"2006","unstructured":"Luca Trevisan . 2006 . Pseudorandomness and combinatorial constructions . In International Congress of Mathematicians. Vol. III . Eur. Math. Soc., Z\u00fcrich, 1111\u2013 1136. Luca Trevisan. 2006. Pseudorandomness and combinatorial constructions. In International Congress of Mathematicians. Vol. III. Eur. Math. Soc., Z\u00fcrich, 1111\u2013 1136."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_2_45_1","unstructured":"Salil P. Vadhan. 2012.  Salil P. Vadhan. 2012."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055500","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:36:20Z","timestamp":1750203380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":45,"alternative-id":["10.1145\/3055399.3055500","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055500","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}