{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:40:19Z","timestamp":1736523619653,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_41","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"471-479","source":"Crossref","is-referenced-by-count":2,"title":["Dimension Characterizations of Complexity Classes"],"prefix":"10.1007","author":[{"given":"Xiaoyang","family":"Gu","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"41_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45294-X_1","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"2001","unstructured":"Allender, E.: When worlds collide: Derandomization, lower bounds, and kolmogorov complexity. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 1\u201315. Springer, Heidelberg (2001)"},{"key":"#cr-split#-41_CR2.1","doi-asserted-by":"crossref","unstructured":"Allender, E., Buhrman, H., Kouck??, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 669???678 (2002);","DOI":"10.1109\/SFCS.2002.1181992"},{"key":"#cr-split#-41_CR2.2","doi-asserted-by":"crossref","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 669\u2013678 (2002); SIAM Journal on Computing (to appear)","DOI":"10.1109\/SFCS.2002.1181992"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Allender, E., Strauss, M.: Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th Symposium on Foundations of Computer Science, pp. 807\u2013818 (1994)","DOI":"10.1109\/SFCS.1994.365713"},{"key":"41_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"J.L. Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I, 2nd edn. Springer, Berlin (1995)","edition":"2"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"Bennett, C.H., Gill, J.: Relative to a random oracle A, P A \u2009\u2260\u2009NP A \u2009\u2260\u2009co\u2009\u2212\u2009NP A with probability 1. SIAM Journal on Computing\u00a010, 96\u2013113 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L.: One-sided versus two-sided randomness. In: Proceedings of the sixteenth Symposium on Theoretical Aspects of Computer Science, pp. 100\u2013109 (1999)","DOI":"10.1007\/3-540-49116-3_9"},{"issue":"2","key":"41_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0019-9958(58)90082-2","volume":"1","author":"N. Chomsky","year":"1958","unstructured":"Chomsky, N., Miller, G.A.: Finite state languages. Information and Control\u00a01(2), 91\u2013112 (1958)","journal-title":"Information and Control"},{"key":"41_CR8","doi-asserted-by":"publisher","DOI":"10.1002\/0470013850","volume-title":"Fractal Geometry: Mathematical Foundations and Applications","author":"K. Falconer","year":"2003","unstructured":"Falconer, K.: Fractal Geometry: Mathematical Foundations and Applications, 2nd edn. Wiley, Chichester (2003)","edition":"2"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: Comparing notions of full derandomization. In: Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 28\u201334 (2001)","DOI":"10.1109\/CCC.2001.933869"},{"key":"41_CR10","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"11","author":"J. Grollman","year":"1988","unstructured":"Grollman, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM J. Comput.\u00a011, 309\u2013335 (1988)","journal-title":"SIAM J. Comput."},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F. Hausdorff","year":"1919","unstructured":"Hausdorff, F.: Dimension und \u00e4usseres Mass. Mathematische Annalen\u00a079, 157\u2013179 (1919)","journal-title":"Mathematische Annalen"},{"key":"41_CR12","unstructured":"Hitchcock, J.M.: Effective fractal dimension: foundations and applications. PhD thesis, Iowa State University (2003)"},{"issue":"3","key":"41_CR13","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2006.01.025","volume":"355","author":"J.M. Hitchcock","year":"2006","unstructured":"Hitchcock, J.M.: Hausdorff dimension and oracle constructions. Theoretical Computer Science\u00a0355(3), 382\u2013388 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"41_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1086649.1086662","volume":"36","author":"J.M. Hitchcock","year":"2005","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: The fractal geometry of complexity classes. SIGACT News\u00a036(3), 24\u201338 (2005)","journal-title":"SIGACT News"},{"issue":"4","key":"41_CR15","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.jcss.2005.10.002","volume":"72","author":"J.M. Hitchcock","year":"2006","unstructured":"Hitchcock, J.M., Vinodchandran, N.V.: Dimension, entropy rates, and compression. Journal of Computer and System Sciences\u00a072(4), 760\u2013782 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"2","key":"41_CR17","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0019-9958(70)90105-1","volume":"16","author":"W. Kuich","year":"1970","unstructured":"Kuich, W.: On the entropy of context-free languages. Information and Control\u00a016(2), 173\u2013200 (1970)","journal-title":"Information and Control"},{"issue":"5","key":"41_CR18","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/0222065","volume":"22","author":"J.H. Lutz","year":"1993","unstructured":"Lutz, J.H.: A pseudorandom oracle characterization of BPP. SIAM Journal on Computing\u00a022(5), 1075\u20131086 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM Journal on Computing\u00a032, 1236\u20131259 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1002\/malq.200310127","volume":"51","author":"J.H. Lutz","year":"2005","unstructured":"Lutz, J.H.: Effective fractal dimensions. Mathematical Logic Quarterly\u00a051, 62\u201372 (2005)","journal-title":"Mathematical Logic Quarterly"},{"key":"41_CR21","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information and Control\u00a09, 602\u2013619 (1966)","journal-title":"Information and Control"},{"key":"41_CR22","first-page":"171","volume-title":"Proceedings of Foundations of the Formal Sciences III","author":"E. Mayordomo","year":"2004","unstructured":"Mayordomo, E.: Effective Hausdorff dimension. In: Proceedings of Foundations of the Formal Sciences III, pp. 171\u2013186. Kluwer Academic Publishers, Dordrecht (2004)"},{"key":"41_CR23","unstructured":"Moser, P.: Relative to P promise-BPP equals APP. Technical Report TR01-68, Electronic Colloquium on Computational Complexity (2001)"},{"key":"41_CR24","unstructured":"Moser, P.: Random nondeterministic real functions and Arthur Merlin games. Technical Report TR02-006, ECCC (2002)"},{"key":"41_CR25","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. Journal of Computer and System Sciences\u00a049, 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1993.1017","volume":"103","author":"L. Staiger","year":"1993","unstructured":"Staiger, L.: Kolmogorov complexity and Hausdorff dimension. Information and Computation\u00a0103, 159\u2013194 (1993)","journal-title":"Information and Computation"},{"key":"41_CR27","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s002240000086","volume":"31","author":"L. Staiger","year":"1998","unstructured":"Staiger, L.: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems\u00a031, 215\u2013229 (1998)","journal-title":"Theory of Computing Systems"},{"key":"41_CR28","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C.B. Wilson","year":"1985","unstructured":"Wilson, C.B.: Relativized circuit complexity. Journal of Computer and System Sciences\u00a031, 169\u2013181 (1985)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:23:16Z","timestamp":1736522596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11821069_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}