{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:24Z","timestamp":1784484144010,"version":"3.55.0"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_22","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:34Z","timestamp":1784482174000},"page":"335-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Random Oracles for\u00a0the\u00a0Polynomial-Time Hierarchy and\u00a0Quantum Complexity Classes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8614-7307","authenticated-orcid":false,"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0404-3029","authenticated-orcid":false,"given":"Adewale","family":"Sekoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1483-6674","authenticated-orcid":false,"given":"Hadi","family":"Shafei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Ingram, D., Kretschmer, W.: The acrobatics of BQP. In: 37th Computational Complexity Conference, pp. 20:1\u201320:17 (2022). https:\/\/doi.org\/10.4230\/LIPICS.CCC.2022.20","DOI":"10.4230\/LIPICS.CCC.2022.20"},{"key":"22_CR2","doi-asserted-by":"publisher","unstructured":"Allender, E., Strauss, M.: Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 807\u2013818. IEEE Computer Society (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365713","DOI":"10.1109\/SFCS.1994.365713"},{"key":"22_CR3","doi-asserted-by":"publisher","unstructured":"Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory, pp. 1\u201347. Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, New York, N.Y. (1997). https:\/\/doi.org\/10.1201\/9780429187490-1","DOI":"10.1201\/9780429187490-1"},{"key":"22_CR4","doi-asserted-by":"publisher","unstructured":"Aspnes, J., Beigel, R., Furst, M., Rudich, S.: The expressive power of voting polynomials. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 402\u2013409. ACM Press (1991). https:\/\/doi.org\/10.1145\/103418.103461","DOI":"10.1145\/103418.103461"},{"key":"22_CR5","doi-asserted-by":"publisher","unstructured":"Babai, L.: Random oracles separate pspace from the polynomial-time hierarchy. Inf. Process. Lett. 26, 51\u201353 (1987). https:\/\/doi.org\/10.1016\/0020-0190(87)90036-6","DOI":"10.1016\/0020-0190(87)90036-6"},{"issue":"5","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/s0097539796300933","volume":"26","author":"CH Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.V.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510\u20131523 (1997). https:\/\/doi.org\/10.1137\/s0097539796300933","journal-title":"SIAM J. Comput."},{"key":"22_CR7","doi-asserted-by":"publisher","unstructured":"Bennett, C.H., Gill, J.: Relative to a random oracle $$A$$, $${\\rm P}^A \\ne {\\rm NP}^A \\ne \\text{co-NP}^A$$ with probability 1. SIAM J. Comput. 10, 96\u2013113 (1981). https:\/\/doi.org\/10.1137\/0210008","DOI":"10.1137\/0210008"},{"key":"22_CR8","doi-asserted-by":"publisher","unstructured":"Book, R.V., Lutz, J.H., Wagner, K.W.: An observation on probability versus randomness with applications to complexity classes. Math. Syst. Theory 27, 201\u2013209 (1994). https:\/\/doi.org\/10.1007\/bf01578842","DOI":"10.1007\/bf01578842"},{"key":"22_CR9","doi-asserted-by":"publisher","unstructured":"Cai, J.: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. J. Comput. Syst. Sci. 38, 68\u201385 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90033-0","DOI":"10.1016\/0022-0000(89)90033-0"},{"issue":"1","key":"22_CR10","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/s0022-0000(05)80084-4","volume":"49","author":"R Chang","year":"1994","unstructured":"Chang, R., et al.: The random oracle hypothesis is false. J. Comput. Syst. Sci. 49(1), 24\u201339 (1994). https:\/\/doi.org\/10.1016\/s0022-0000(05)80084-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"22_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/s0022-0000(05)80024-8","volume":"48","author":"SA Fenner","year":"1994","unstructured":"Fenner, S.A., Fortnow, L., Kurtz, S.A.: Gap-definable counting classes. J. Comput. Syst. Sci. 48(1), 116\u2013148 (1994). https:\/\/doi.org\/10.1016\/s0022-0000(05)80024-8","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR12","doi-asserted-by":"publisher","unstructured":"Fenner, S., Green, F., Homer, S., Pruim, R.: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. R. Soc. Lond. Series A: Math. Phys. Eng. Sci. 455(1991), 3953\u20133966 (1999). https:\/\/doi.org\/10.1098\/rspa.1999.0485","DOI":"10.1098\/rspa.1999.0485"},{"key":"22_CR13","doi-asserted-by":"publisher","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial time hierarchy. In: Proceedings of the Twenty-second Annual IEEE Symposium on Foundations of Computer Science, pp. 260\u2013270. (1981). https:\/\/doi.org\/10.1109\/sfcs.1981.35","DOI":"10.1109\/sfcs.1981.35"},{"key":"22_CR14","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325\u2013328 (1997). https:\/\/doi.org\/10.1103\/physrevlett.79.325","DOI":"10.1103\/physrevlett.79.325"},{"key":"22_CR15","unstructured":"H\u00e5stad, J.: Computational Limitations for Small-Depth Circuits. The MIT Press, Cambridge (1986)"},{"key":"22_CR16","doi-asserted-by":"publisher","unstructured":"H\u00e5stad, J., Rossman, B., Servedio, R.A., Tan, L.: An average-case depth hierarchy theorem for Boolean circuits. J. ACM 64(5), 35:1\u201335:27 (2017). https:\/\/doi.org\/10.1145\/3095799","DOI":"10.1145\/3095799"},{"issue":"3","key":"22_CR17","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2006.01.025","volume":"355","author":"JM Hitchcock","year":"2006","unstructured":"Hitchcock, J.M.: Hausdorff dimension and oracle constructions. Theor. Comput. Sci. 355(3), 382\u2013388 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.01.025","journal-title":"Theor. Comput. Sci."},{"key":"22_CR18","doi-asserted-by":"publisher","unstructured":"Hitchcock, J.M., Sekoni, A., Shafei, H.: Polynomial-time random oracles and separating complexity classes. ACM Trans. Comput. Theory 13(1) (2021). https:\/\/doi.org\/10.1145\/3434389","DOI":"10.1145\/3434389"},{"key":"22_CR19","doi-asserted-by":"publisher","unstructured":"Hitchcock, J.M., Sekoni, A., Shafei, H.: Counting martingales for measure and dimension in complexity classes. In: Proceedings of the 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0339, pp. 20:1\u201320:35 (2025). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2025.20","DOI":"10.4230\/LIPIcs.CCC.2025.20"},{"issue":"4","key":"22_CR20","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.jcss.2005.10.002","volume":"72","author":"JM Hitchcock","year":"2006","unstructured":"Hitchcock, J.M., Vinodchandran, N.V.: Dimension, entropy rates, and compression. J. Comput. Syst. Sci. 72(4), 760\u2013782 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2005.10.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"22_CR21","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF00276023","volume":"26","author":"J K\u00f6bler","year":"1989","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Toran, J.: On counting and approximation. Acta Informatica 26(4), 363\u2013379 (1989). https:\/\/doi.org\/10.1007\/BF00276023","journal-title":"Acta Informatica"},{"key":"22_CR22","unstructured":"Kretschmer, W.: QMA lower bounds for approximate counting. Tech. rep., arXiv (2019)"},{"issue":"6","key":"22_CR23","doi-asserted-by":"publisher","first-page":"183","DOI":"10.4086\/toc.2015.v011a006","volume":"11","author":"G Kuperberg","year":"2015","unstructured":"Kuperberg, G.: How hard is it to approximate the Jones polynomial? Theory Comput. 11(6), 183\u2013219 (2015). https:\/\/doi.org\/10.4086\/toc.2015.v011a006","journal-title":"Theory Comput."},{"key":"22_CR24","doi-asserted-by":"publisher","unstructured":"Kurtz, S.: On the random oracle hypothesis. Information Control 57, 40\u201347 (1983). https:\/\/doi.org\/10.1016\/s0019-9958(83)80023-0","DOI":"10.1016\/s0019-9958(83)80023-0"},{"key":"22_CR25","unstructured":"Li, L.: On the counting functions. Ph.D. thesis, University of Chicago (1993). https:\/\/www.proquest.com\/dissertations-theses\/on-counting-functions\/docview\/304080357\/se-2"},{"issue":"6","key":"22_CR26","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"JH Lutz","year":"1990","unstructured":"Lutz, J.H.: Category and measure in complexity classes. SIAM J. Comput. 19(6), 1100\u20131131 (1990). https:\/\/doi.org\/10.1137\/0219076","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR27","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-j","volume":"44","author":"JH Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992). https:\/\/doi.org\/10.1016\/0022-0000(92)90020-j","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR28","doi-asserted-by":"publisher","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013254. Springer, Cham (1997). https:\/\/doi.org\/10.1007\/978-1-4612-1872-2_10","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"22_CR29","doi-asserted-by":"publisher","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236\u20131259 (2003). https:\/\/doi.org\/10.1137\/S0097539701417723","DOI":"10.1137\/S0097539701417723"},{"key":"22_CR30","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bull. Eur. Assoc. Theor. Comput. Sci. 68, 64\u201380 (1999). also appears as ch22Lutz:TPRBM01"},{"key":"22_CR31","doi-asserted-by":"publisher","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. In: P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science: Entering the 21st Century, pp. 83\u2013101. World Scientific Publishing (2001). https:\/\/doi.org\/10.1142\/9789812810403_0001","DOI":"10.1142\/9789812810403_0001"},{"key":"22_CR32","doi-asserted-by":"publisher","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information Control 9, 602\u2013619 (1966). https:\/\/doi.org\/10.1016\/s0019-9958(66)80018-9","DOI":"10.1016\/s0019-9958(66)80018-9"},{"issue":"2","key":"22_CR33","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-c","volume":"136","author":"E Mayordomo","year":"1994","unstructured":"Mayordomo, E.: Almost every set in exponential time is P-bi-immune. Theor. Comput. Sci. 136(2), 487\u2013506 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)00023-c","journal-title":"Theor. Comput. Sci."},{"key":"22_CR34","unstructured":"Mayordomo, E.: Contributions to the study of resource-bounded measure. Ph.D. thesis, Universitat Polit\u00e8cnica de Catalunya (1994). https:\/\/eccc.weizmann.ac.il\/static\/books\/Contributions_to_the_Study_of_Resource_Bounded_Measure\/"},{"issue":"1\u20132","key":"22_CR35","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/s0304-3975(00)00191-2","volume":"244","author":"D van Melkebeek","year":"2000","unstructured":"van Melkebeek, D.: The zero-one law holds for BPP. Theor. Comput. Sci. 244(1\u20132), 283\u2013288 (2000). https:\/\/doi.org\/10.1016\/s0304-3975(00)00191-2","journal-title":"Theor. Comput. Sci."},{"key":"22_CR36","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. In: Theoretical Computer Science: 6th Gl-Conference Dortmund, January 5\u20137, 1983, LNCS, pp. 269\u2013275. Springer, Cham (1982). https:\/\/doi.org\/10.1007\/BFB0009651","DOI":"10.1007\/BFB0009651"},{"key":"22_CR37","doi-asserted-by":"publisher","unstructured":"Rossman, B., Servedio, R.A., Tan, L.Y.: An average-case depth hierarchy theorem for Boolean circuits. In: Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pp. 1030\u20131048. IEEE (2015). https:\/\/doi.org\/10.1109\/focs.2015.67","DOI":"10.1109\/focs.2015.67"},{"issue":"4","key":"22_CR38","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/2852040.2852052","volume":"46","author":"B Rossman","year":"2015","unstructured":"Rossman, B., Servedio, R.A., Tan, L.: Complexity theory column 89: the polynomial hierarchy, random oracles, and Boolean circuits. ACM SIGACT News 46(4), 50\u201368 (2015). https:\/\/doi.org\/10.1145\/2852040.2852052","journal-title":"ACM SIGACT News"},{"key":"22_CR39","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J.: On approximation algorithms for #P. SIAM J. Comput. 14, 849\u2013861 (1985). https:\/\/doi.org\/10.1137\/0214060","DOI":"10.1137\/0214060"},{"issue":"2","key":"22_CR40","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S Toda","year":"1992","unstructured":"Toda, S., Ogiwara, M.: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput. 21(2), 316\u2013328 (1992). https:\/\/doi.org\/10.1137\/0221023","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR41","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor. Comput. Sci."},{"key":"22_CR42","doi-asserted-by":"publisher","unstructured":"Vollmer, H., Wagner, K.W.: Measure one results in computational complexity theory. In: Du, D.Z., Ko, K.I. (eds.) Advances in Algorithms, Languages, and Complexity, LNCS, pp. 285\u2013312. Springer, US, Boston, MA (1997). https:\/\/doi.org\/10.1007\/978-1-4613-3394-4_14","DOI":"10.1007\/978-1-4613-3394-4_14"},{"key":"22_CR43","unstructured":"Vyalyi, M.N.: QMA = PP implies that PP contains PH. Tech. Rep. 03-021, ECCC (2003). https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2003\/TR03-021\/index.html"},{"issue":"3","key":"22_CR44","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W.: The complexity of combinatorial problems with succinct input representation. Acta Informatica 23(3), 325\u2013356 (1986). https:\/\/doi.org\/10.1007\/BF00289117","journal-title":"Acta Informatica"},{"key":"22_CR45","doi-asserted-by":"publisher","unstructured":"Yao, A.: Separating the polynomial-time hierarchy by oracles. In: 26th IEEE Symposium on Foundations of Computer Science, pp. 1\u201310. IEEE Computer Society Press (1985). https:\/\/doi.org\/10.1109\/sfcs.1985.49","DOI":"10.1109\/sfcs.1985.49"}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:35Z","timestamp":1784482175000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}