{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:24:35Z","timestamp":1787509475595,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Japan Society for the Promotion of Science","award":["18H04090"],"award-info":[{"award-number":["18H04090"]}]},{"name":"ACT-I, JST"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384251","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"1038-1051","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Unexpected hardness results for Kolmogorov complexity under uniform reductions"],"prefix":"10.1145","author":[{"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30870-3_2"},{"key":"e_1_3_2_1_2_1","volume-title":"Computability and Complexity-Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. 79-94.","author":"Allender Eric","unstructured":"Eric Allender . 2017. The Complexity of Complexity . In Computability and Complexity-Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. 79-94. Eric Allender. 2017. The Complexity of Complexity. In Computability and Complexity-Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. 79-94."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Eric Allender Harry Buhrman Luke Friedman and Bruno Lof. 2014. Reductions to the set of random strings: The resource-bounded case. Logical Methods in Computer Science 10 3 ( 2014 ). Eric Allender Harry Buhrman Luke Friedman and Bruno Lof. 2014. Reductions to the set of random strings: The resource-bounded case. Logical Methods in Computer Science 10 3 ( 2014 ).","DOI":"10.2168\/LMCS-10(3:5)2014"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.06.003"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Eric Allender and Bireswar Das. 2017. Zero knowledge and circuit minimization. Inf. Comput. 256 ( 2017 ) 2-8. Eric Allender and Bireswar Das. 2017. Zero knowledge and circuit minimization. Inf. Comput. 256 ( 2017 ) 2-8.","DOI":"10.1016\/j.ic.2017.04.004"},{"key":"e_1_3_2_1_7_1","unstructured":"Eric Allender George Davie Luke Friedman Samuel Hopkins and Iddo Tzameret. 2013. Kolmogorov Complexity Circuits and the Strength of Formal Theories of Arithmetic. Chicago J. Theor. Comput. Sci. 2013 ( 2013 ). Eric Allender George Davie Luke Friedman Samuel Hopkins and Iddo Tzameret. 2013. Kolmogorov Complexity Circuits and the Strength of Formal Theories of Arithmetic. Chicago J. Theor. Comput. Sci. 2013 ( 2013 )."},{"key":"e_1_3_2_1_8_1","volume-title":"Gasarch","author":"Allender Eric","year":"2013","unstructured":"Eric Allender , Luke Friedman , and William I . Gasarch . 2013 . Limits on the computational power of random strings. Inf. Comput . 222 ( 2013 ), 80-92. Eric Allender, Luke Friedman, and William I. Gasarch. 2013. Limits on the computational power of random strings. Inf. Comput. 222 ( 2013 ), 80-92."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/060664537"},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems","volume":"54","author":"Allender Eric","year":"2017","unstructured":"Eric Allender and Shuichi Hirahara . 2017 . New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems . In MFCS. 54 : 1 - 54 : 14. Eric Allender and Shuichi Hirahara. 2017. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. In MFCS. 54 : 1-54 : 14.","journal-title":"MFCS."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Eric Allender Dhiraj Holden and Valentine Kabanets. 2017. The Minimum Oracle Circuit Size Problem. Computational Complexity 26 2 ( 2017 ) 469-496. Eric Allender Dhiraj Holden and Valentine Kabanets. 2017. The Minimum Oracle Circuit Size Problem. Computational Complexity 26 2 ( 2017 ) 469-496.","DOI":"10.1007\/s00037-016-0124-0"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.004"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Eric Allender and Holger Spakowski. 2012. Avoiding Simplicity is Complex. Theory Comput. Syst. 51 3 ( 2012 ) 282-296. Eric Allender and Holger Spakowski. 2012. Avoiding Simplicity is Complex. Theory Comput. Syst. 51 3 ( 2012 ) 282-296.","DOI":"10.1007\/s00224-011-9334-7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai Lance Fortnow and Carsten Lund. 1991. Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1 ( 1991 ) 3-40. L\u00e1szl\u00f3 Babai Lance Fortnow and Carsten Lund. 1991. Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1 ( 1991 ) 3-40.","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai Lance Fortnow Noam Nisan and Avi Wigderson. 1993. BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3 ( 1993 ) 307-318. L\u00e1szl\u00f3 Babai Lance Fortnow Noam Nisan and Avi Wigderson. 1993. BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3 ( 1993 ) 307-318.","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_1_17_1","first-page":"58","article-title":"Derandomizing from Random Strings","author":"Buhrman Harry","year":"2010","unstructured":"Harry Buhrman , Lance Fortnow , Michal Kouck\u00fd , and Bruno Lof . 2010 . Derandomizing from Random Strings . In CCC. 58 - 63 . Harry Buhrman, Lance Fortnow, Michal Kouck\u00fd, and Bruno Lof. 2010. Derandomizing from Random Strings. In CCC. 58-63.","journal-title":"CCC."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1484"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360148"},{"key":"e_1_3_2_1_20_1","unstructured":"J. Comput. Syst. Sci. 2007 73 Sp2 \u2286 ZPPNP"},{"key":"e_1_3_2_1_21_1","volume-title":"Miller","author":"Cai Mingzhong","year":"2014","unstructured":"Mingzhong Cai , Rodney G. Downey , Rachel Epstein , Stefen Lempp , and Joseph S . Miller . 2014 . Random strings and tt-degrees of Turing complete C.E. sets. Logical Methods in Computer Science 10, 3 ( 2014 ). Mingzhong Cai, Rodney G. Downey, Rachel Epstein, Stefen Lempp, and Joseph S. Miller. 2014. Random strings and tt-degrees of Turing complete C.E. sets. Logical Methods in Computer Science 10, 3 ( 2014 )."},{"key":"e_1_3_2_1_22_1","article-title":"More on BPP and the Polynomial-Time","volume":"57","author":"Canetti Ran","year":"1996","unstructured":"Ran Canetti . 1996 . More on BPP and the Polynomial-Time Hierarchy. Inf. Process. Lett. 57 , 5 ( 1996 ), 237-241. Ran Canetti. 1996. More on BPP and the Polynomial-Time Hierarchy. Inf. Process. Lett. 57, 5 ( 1996 ), 237-241.","journal-title":"Hierarchy. Inf. Process. Lett."},{"key":"e_1_3_2_1_23_1","first-page":"151","article-title":"The Complexity of Theorem-Proving Procedures","author":"Cook Stephen A.","year":"1971","unstructured":"Stephen A. Cook . 1971 . The Complexity of Theorem-Proving Procedures . In STOC. 151 - 158 . Stephen A. Cook. 1971. The Complexity of Theorem-Proving Procedures. In STOC. 151-158.","journal-title":"STOC."},{"key":"e_1_3_2_1_24_1","volume-title":"ICALP Satellite Workshops. 77-84","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich and Avi Wigderson . 2000 . On Pseudorandomness with respect to Deterministic Observes . In ICALP Satellite Workshops. 77-84 . Oded Goldreich and Avi Wigderson. 2000. On Pseudorandomness with respect to Deterministic Observes. In ICALP Satellite Workshops. 77-84."},{"key":"e_1_3_2_1_25_1","first-page":"469","article-title":"Limitations of Hardness vs. Randomness under Uniform Reductions","author":"Gutfreund Dan","year":"2008","unstructured":"Dan Gutfreund and Salil P. Vadhan . 2008 . Limitations of Hardness vs. Randomness under Uniform Reductions . In APPROX. 469 - 482 . Dan Gutfreund and Salil P. Vadhan. 2008. Limitations of Hardness vs. Randomness under Uniform Reductions. In APPROX. 469-482.","journal-title":"APPROX."},{"key":"e_1_3_2_1_26_1","first-page":"439","article-title":"Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)","author":"Hartmanis Juris","year":"1983","unstructured":"Juris Hartmanis . 1983 . Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report) . In FOCS. 439 - 445 . Juris Hartmanis. 1983. Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report). In FOCS. 439-445.","journal-title":"FOCS."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Juris Hartmanis and Richard E Stearns. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 ( 1965 ) 285-306. Juris Hartmanis and Richard E Stearns. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 ( 1965 ) 285-306.","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"e_1_3_2_1_28_1","first-page":"244","article-title":"Identifying an Honest EXPNP Oracle Among Many","author":"Hirahara Shuichi","year":"2015","unstructured":"Shuichi Hirahara . 2015 . Identifying an Honest EXPNP Oracle Among Many . In CCC. 244 - 263 . Shuichi Hirahara. 2015. Identifying an Honest EXPNP Oracle Among Many. In CCC. 244-263.","journal-title":"CCC."},{"key":"e_1_3_2_1_29_1","first-page":"247","article-title":"Non-black-box Worst-case to Average-case Reductions within NP","author":"Hirahara Shuichi","year":"2018","unstructured":"Shuichi Hirahara . 2018 . Non-black-box Worst-case to Average-case Reductions within NP . In FOCS. 247 - 258 . Shuichi Hirahara. 2018. Non-black-box Worst-case to Average-case Reductions within NP. In FOCS. 247-258.","journal-title":"FOCS."},{"key":"e_1_3_2_1_30_1","first-page":"1","article-title":"Unexpected Power of Random Strings","volume":"41","author":"Hirahara Shuichi","year":"2020","unstructured":"Shuichi Hirahara . 2020 . Unexpected Power of Random Strings . In ITCS. 41 : 1 - 41 : 13. Shuichi Hirahara. 2020. Unexpected Power of Random Strings. In ITCS. 41 : 1-41 : 13.","journal-title":"ITCS."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Shuichi Hirahara and Akitoshi Kawamura. 2018. On characterizations of randomized computation using plain Kolmogorov complexity. Computability 7 1 ( 2018 ) 45-56. Shuichi Hirahara and Akitoshi Kawamura. 2018. On characterizations of randomized computation using plain Kolmogorov complexity. Computability 7 1 ( 2018 ) 45-56.","DOI":"10.3233\/COM-170075"},{"key":"e_1_3_2_1_32_1","first-page":"1","article-title":"NPhardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits","volume":"5","author":"Hirahara Shuichi","year":"2018","unstructured":"Shuichi Hirahara , Igor Carboni Oliveira , and Rahul Santhanam . 2018 . NPhardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits . In CCC. 5 : 1 - 5 : 31. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. 2018. NPhardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. In CCC. 5:1-5 : 31.","journal-title":"CCC."},{"key":"e_1_3_2_1_33_1","first-page":"1","article-title":"Limits of Minimum Circuit Size Problem as Oracle","volume":"18","author":"Hirahara Shuichi","year":"2016","unstructured":"Shuichi Hirahara and Osamu Watanabe . 2016 . Limits of Minimum Circuit Size Problem as Oracle . In CCC. 18 : 1 - 18 : 20. Shuichi Hirahara and Osamu Watanabe. 2016. Limits of Minimum Circuit Size Problem as Oracle. In CCC. 18 : 1-18 : 20.","journal-title":"CCC."},{"key":"e_1_3_2_1_34_1","unstructured":"Shuichi Hirahara and Osamu Watanabe. 2019. On Nonadaptive Security Reductions of Hitting Set Generators. ( 2019 ). ECCC TR19-025. Shuichi Hirahara and Osamu Watanabe. 2019. On Nonadaptive Security Reductions of Hitting Set Generators. ( 2019 ). ECCC TR19-025."},{"key":"e_1_3_2_1_35_1","first-page":"236","article-title":"On the NP-Completeness of the Minimum Circuit Size Problem","author":"Hitchcock John M.","year":"2015","unstructured":"John M. Hitchcock and Aduri Pavan . 2015 . On the NP-Completeness of the Minimum Circuit Size Problem . In FSTTCS. 236 - 245 . John M. Hitchcock and Aduri Pavan. 2015. On the NP-Completeness of the Minimum Circuit Size Problem. In FSTTCS. 236-245.","journal-title":"FSTTCS."},{"key":"e_1_3_2_1_36_1","first-page":"1","article-title":"Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p]","volume":"34","author":"Ilango Rahul","year":"2020","unstructured":"Rahul Ilango . 2020 . Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p] . In ITCS. 34 : 1 - 34 : 26. Rahul Ilango. 2020. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p]. In ITCS. 34 : 1-34 : 26.","journal-title":"ITCS."},{"key":"e_1_3_2_1_37_1","first-page":"1","article-title":"The Power of Natural Properties as Oracles","volume":"7","author":"Impagliazzo Russell","year":"2018","unstructured":"Russell Impagliazzo , Valentine Kabanets , and Ilya Volkovich . 2018 . The Power of Natural Properties as Oracles . In CCC. 7 : 1 - 7 : 20. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. 2018. The Power of Natural Properties as Oracles. In CCC. 7:1-7 : 20.","journal-title":"CCC."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/335305.335314","article-title":"Circuit minimization problem","author":"Kabanets Valentine","year":"2000","unstructured":"Valentine Kabanets and Jin-yi Cai. 2000 . Circuit minimization problem . In STOC. 73 - 79 . Valentine Kabanets and Jin-yi Cai. 2000. Circuit minimization problem. In STOC. 73-79.","journal-title":"STOC."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Ker-I Ko. 1986. On the Notion of Infinite Pseudorandom Sequences. Theor. Comput. Sci. 48 3 ( 1986 ) 9-33. Ker-I Ko. 1986. On the Notion of Infinite Pseudorandom Sequences. Theor. Comput. Sci. 48 3 ( 1986 ) 9-33.","DOI":"10.1016\/0304-3975(86)90081-2"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"e_1_3_2_1_43_1","first-page":"46","article-title":"Proofs, Codes, and Polynomial-Time Reducibilities","author":"Kumar Ravi","year":"1999","unstructured":"Ravi Kumar and D. Sivakumar . 1999 . Proofs, Codes, and Polynomial-Time Reducibilities . In CCC. 46 - 53 . Ravi Kumar and D. Sivakumar. 1999. Proofs, Codes, and Polynomial-Time Reducibilities. In CCC. 46-53.","journal-title":"CCC."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.017"},{"key":"e_1_3_2_1_45_1","unstructured":"Leonid Anatolevich Levin. 1973. Universal sequential search problems. Problemy Peredachi Informatsii 9 3 ( 1973 ) 115-116. Leonid Anatolevich Levin. 1973. Universal sequential search problems. Problemy Peredachi Informatsii 9 3 ( 1973 ) 115-116."},{"key":"e_1_3_2_1_46_1","volume-title":"Randomness Conservation Inequalities","author":"Levin Leonid A.","year":"1984","unstructured":"Leonid A. Levin . 1984. Randomness Conservation Inequalities ; Information and Independence in Mathematical Theories. Information and Control 61, 1 ( 1984 ), 15-37. Leonid A. Levin. 1984. Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Information and Control 61, 1 ( 1984 ), 15-37."},{"key":"e_1_3_2_1_47_1","volume-title":"Vit\u00e1nyi","author":"Li Ming","year":"2008","unstructured":"Ming Li and Paul M. B . Vit\u00e1nyi . 2008 . An Introduction to Kolmogorov Complexity and Its Applications, Third Edition. Springer . Ming Li and Paul M. B. Vit\u00e1nyi. 2008. An Introduction to Kolmogorov Complexity and Its Applications, Third Edition. Springer."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Luc Longpr\u00e9 and Osamu Watanabe. 1995. On Symmetry of Information and Polynomial Time Invertibility. Inf. Comput. 121 1 ( 1995 ) 14-22. Luc Longpr\u00e9 and Osamu Watanabe. 1995. On Symmetry of Information and Polynomial Time Invertibility. Inf. Comput. 121 1 ( 1995 ) 14-22.","DOI":"10.1006\/inco.1995.1120"},{"key":"e_1_3_2_1_49_1","unstructured":"William J Masek. 1979. Some NP-complete set covering problems. Unpublished manuscript ( 1979 ). William J Masek. 1979. Some NP-complete set covering problems. Unpublished manuscript ( 1979 )."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Cody D. Murray and R. Ryan Williams. 2017. On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing 13 1 ( 2017 ) 1-22. Cody D. Murray and R. Ryan Williams. 2017. On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing 13 1 ( 2017 ) 1-22.","DOI":"10.4086\/toc.2017.v013a004"},{"key":"e_1_3_2_1_51_1","first-page":"1","article-title":"Randomness and Intractability in Kolmogorov Complexity","volume":"32","author":"Oliveira Igor Carboni","year":"2019","unstructured":"Igor Carboni Oliveira . 2019 . Randomness and Intractability in Kolmogorov Complexity . In ICALP. 32 : 1 - 32 : 14. Igor Carboni Oliveira. 2019. Randomness and Intractability in Kolmogorov Complexity. In ICALP. 32 : 1-32 : 14.","journal-title":"ICALP."},{"key":"e_1_3_2_1_52_1","unstructured":"Detlef Ronneburger. 2004. Kolmogorov Complexity and Derandomization. ( 2004 ). Detlef Ronneburger. 2004. Kolmogorov Complexity and Derandomization. ( 2004 )."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Alexander Russell and Ravi Sundaram. 1998. Symmetric Alternation Captures BPP. Computational Complexity 7 2 ( 1998 ) 152-162. Alexander Russell and Ravi Sundaram. 1998. Symmetric Alternation Captures BPP. Computational Complexity 7 2 ( 1998 ) 152-162.","DOI":"10.1007\/s000370050007"},{"key":"e_1_3_2_1_54_1","first-page":"330","article-title":"A Complexity Theoretic Approach to Randomness","author":"Sipser Michael","year":"1983","unstructured":"Michael Sipser . 1983 . A Complexity Theoretic Approach to Randomness . In STOC. 330 - 335 . Michael Sipser. 1983. A Complexity Theoretic Approach to Randomness. In STOC. 330-335.","journal-title":"STOC."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_57_1","volume-title":"Vadhan","author":"Trevisan Luca","year":"2007","unstructured":"Luca Trevisan and Salil P . Vadhan . 2007 . Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16, 4 ( 2007 ), 331-364. Luca Trevisan and Salil P. Vadhan. 2007. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16, 4 ( 2007 ), 331-364."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_59_1","volume-title":"Vazirani","author":"Vazirani Umesh V.","year":"1983","unstructured":"Umesh V. Vazirani and Vijay V . Vazirani . 1983 . A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. Theor. Comput. Sci . 24 ( 1983 ), 291-300. Umesh V. Vazirani and Vijay V. Vazirani. 1983. A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. Theor. Comput. Sci. 24 ( 1983 ), 291-300."},{"key":"e_1_3_2_1_60_1","first-page":"335","article-title":"Randomness and the Density of Hard Problems","author":"Wilber Robert E.","year":"1983","unstructured":"Robert E. Wilber . 1983 . Randomness and the Density of Hard Problems . In FOCS. 335 - 342 . Robert E. Wilber. 1983. Randomness and the Density of Hard Problems. In FOCS. 335-342.","journal-title":"FOCS."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384251","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":62,"alternative-id":["10.1145\/3357713.3384251","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384251","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}