{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:52:35Z","timestamp":1770817955738,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030416713","type":"print"},{"value":"9783030416720","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41672-0_6","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T02:03:04Z","timestamp":1582164184000},"page":"67-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets"],"prefix":"10.1007","author":[{"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 701\u2013710 (2006)","DOI":"10.1145\/1132516.1132614"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: Erratum for: on basing one-way functions on NP-hardness. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 795\u2013796 (2010)","DOI":"10.1145\/1806689.1806798"},{"issue":"6","key":"6_CR3","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(6), 1467\u20131493 (2006)","journal-title":"SIAM J. Comput."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2017.04.004","volume":"256","author":"E Allender","year":"2017","unstructured":"Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2\u20138 (2017)","journal-title":"Inf. Comput."},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.ic.2011.09.008","volume":"222","author":"E Allender","year":"2013","unstructured":"Allender, E., Friedman, L., Gasarch, W.I.: Limits on the computational power of random strings. Inf. Comput. 222, 80\u201392 (2013)","journal-title":"Inf. Comput."},{"issue":"4","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3349616","volume":"11","author":"Eric Allender","year":"2019","unstructured":"Allender, E., Hirahara, S.: New insights on the (non-) hardness of circuit minimization and related problems. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 54:1\u201354:14 (2017)","journal-title":"ACM Transactions on Computation Theory"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Xiao, D.: On basing lower-bounds for learning on worst-case assumptions. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 211\u2013220 (2008)","DOI":"10.1109\/FOCS.2008.35"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-46494-6_1","volume-title":"Theory of Cryptography","author":"A Bogdanov","year":"2015","unstructured":"Bogdanov, A., Brzuska, C.: On basing size-verifiable one-way functions on NP-hardness. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 1\u20136. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46494-6_1"},{"issue":"4","key":"6_CR9","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM J. Comput. 36(4), 1119\u20131159 (2006)","journal-title":"SIAM J. Comput."},{"key":"6_CR10","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: Proceedings of the Conference on Computational Complexity (CCC), pp. 10:1\u201310:24 (2016)"},{"issue":"5","key":"6_CR11","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM J. Comput. 22(5), 994\u20131005 (1993)","journal-title":"SIAM J. Comput."},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"327","DOI":"10.2190\/4U1D-VQRM-J70D-JEQF","volume":"5","author":"L Fortnow","year":"1989","unstructured":"Fortnow, L.: The complexity of perfect zero-knowledge. Adv. Comput. Res. 5, 327\u2013343 (1989)","journal-title":"Adv. Comput. Res."},{"issue":"4","key":"6_CR13","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 59\u201368 (1986)","DOI":"10.1145\/12130.12137"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-540-85363-3_37","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"D Gutfreund","year":"2008","unstructured":"Gutfreund, D., Vadhan, S.: Limitations of hardness vs. randomness under uniform reductions. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX\/RANDOM -2008. LNCS, vol. 5171, pp. 469\u2013482. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85363-3_37"},{"issue":"3","key":"6_CR16","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1137\/100814421","volume":"42","author":"I Haitner","year":"2013","unstructured":"Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput. 42(3), 1405\u20131430 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"6_CR17","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 247\u2013258 (2018)","DOI":"10.1109\/FOCS.2018.00032"},{"key":"6_CR19","unstructured":"Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: Proceedings of the Computational Complexity Conference (CCC), pp. 7:1\u20137:20 (2017)"},{"key":"6_CR20","unstructured":"Hirahara, S., Watanabe, O.: Limits of minimum circuit size problem as oracle. In: Proceedings of the Conference on Computational Complexity (CCC), pp. 18:1\u201318:20 (2016)"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Hirahara, S., Watanabe, O.: On nonadaptive reductions to the set of random strings and its dense subsets. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 26, p. 25 (2019)","DOI":"10.1007\/978-3-030-41672-0_6"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Holenstein, T.: Key agreement from weak bit agreement. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 664\u2013673 (2005)","DOI":"10.1145\/1060590.1060689"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/11681878_23","volume-title":"Theory of Cryptography","author":"T Holenstein","year":"2006","unstructured":"Holenstein, T.: Pseudorandom generators from one-way functions: a simple construction for any hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443\u2013461. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11681878_23"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.: Circuit minimization problem. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0304-3975(87)90078-8","volume":"52","author":"K Ko","year":"1987","unstructured":"Ko, K.: On helping by robust oracle machines. Theor. Comput. Sci. 52, 15\u201336 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"6_CR26","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1137\/0220059","volume":"20","author":"K Ko","year":"1991","unstructured":"Ko, K.: On the complexity of learning minimum time-bounded turing machines. SIAM J. Comput. 20(5), 962\u2013986 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"LA Levin","year":"1984","unstructured":"Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15\u201337 (1984)","journal-title":"Inf. Control"},{"issue":"2","key":"6_CR28","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs Randomness. J. Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR29","unstructured":"Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the Structure in Complexity Theory Conference, pp. 133\u2013138 (1991)"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"AA Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-63248-4_8","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"S Rudich","year":"1997","unstructured":"Rudich, S.: Super-bits, demi-bits, and NP\/qpoly-natural proofs. In: Rolim, J. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 85\u201393. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63248-4_8"},{"issue":"4","key":"6_CR32","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.P.: Pseudorandomness and average-case complexity via uniform reductions. Comput. Complex. 16(4), 331\u2013364 (2007)","journal-title":"Comput. Complex."},{"issue":"4","key":"6_CR33","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1137\/S0097539705447207","volume":"36","author":"SP Vadhan","year":"2006","unstructured":"Vadhan, S.P.: An unconditional study of computational zero knowledge. SIAM J. Comput. 36(4), 1160\u20131214 (2006)","journal-title":"SIAM J. Comput."},{"key":"6_CR34","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C Yap","year":"1983","unstructured":"Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T22:28:58Z","timestamp":1665872938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}