{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T03:10:01Z","timestamp":1737342601830,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"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":[[2000]]},"DOI":"10.1007\/3-540-46541-3_6","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"74-86","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bias Invariance of Small Upper Spans"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP. In Proceedings of the 35th Symposium on Foundations of Computer Science, pages 807\u2013818, Piscataway, NJ, 1994. IEEE Computer Society Press.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"6_CR2","unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 1992."},{"key":"6_CR3","series-title":"Lecture Notes in Pure and Applied Mathematics","first-page":"1","volume-title":"Complexity, Logic and Recursion Theory","author":"K. Ambos-Spies","year":"1997","unstructured":"K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pages 1\u201347. Marcel Dekker, New York, N.Y., 1997."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science, 168:3\u201319, 1996.","journal-title":"Theoretical Computer Science"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539796302269","volume":"29","author":"J. M. Breutzmann","year":"2000","unstructured":"J. M. Breutzmann and J. H. Lutz. Equivalence of measures of complexity classes. SIAM Journal on Computing, 29:302\u2013326, 2000.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Torenvliet. Complete sets and structure in subrecursive classes. In Proceedings of Logic Colloquium\u2019 96, pages 45\u201378. Springer-Verlag, 1998.","DOI":"10.1017\/9781316716816.003"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"H. Buhrman and D. van Melkebeek. Hard sets are hard to find. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 170\u2013181, New York, 1998. IEEE.","DOI":"10.1109\/CCC.1998.694602"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, and M. Strauss. A generalization of resource-bounded measure, with an application. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pages 161\u2013171, Berlin, 1998. Springer-Verlag.","DOI":"10.1007\/BFb0028558"},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24(2):279\u2013295, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(95)80016-6","volume":"143","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. Weak completeness in E and E2. Theoretical Computer Science, 143:149\u2013158, 1995.","journal-title":"Theoretical Computer Science"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1006\/inco.1996.0017","volume":"125","author":"D. W. Juedes","year":"1996","unstructured":"D. W. Juedes and J. H. Lutz. Completeness and weak completeness under polynomial-size circuits. Information and Computation, 125:13\u201331, 1996.","journal-title":"Information and Computation"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"214","DOI":"10.2307\/1969123","volume":"49","author":"S. Kakutani","year":"1948","unstructured":"S. Kakutani. On the equivalence of infinite product measures. Annals of Mathematics, 49:214\u2013224, 1948.","journal-title":"Annals of Mathematics"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"S. M. Kautz. Resource-bounded randomness and compressibility with repsect to nonuniform measures. In Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, pages 197\u2013211. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-63248-4_17"},{"key":"6_CR14","unstructured":"W. Lindner. On the polynomial time bounded measure of one-truth-table degrees and p-selectivity, 1993. Diplomarbeit, Technische Universit\u00e4t Berlin."},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In L.A. Hemaspaandra and A.L. Selman, editors, Complexity Theory Retrospective II, pages 225\u2013254. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Resource-bounded measure. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236\u2013248, New York, 1998. IEEE.","DOI":"10.1109\/CCC.1998.694611"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. H. Lutz","year":"1994","unstructured":"J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23:762\u2013779, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"K. W. Regan, D. Sivakumar, and J. Cai. Pseudorandom generators, measure theory, and natural proofs. In 36th IEEE Symposium on Foundations of Computer Science, pages 26\u201335. IEEE Computer Society Press, 1995.","DOI":"10.1109\/SFCS.1995.492459"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00538763","volume":"16","author":"C. P. Schnorr","year":"1970","unstructured":"C. P. Schnorr. Klassifikation der Zufallsgesetze nach Komplexit\u00e4t und Ordnung. Z. Wahrscheinlichkeitstheorie verw. Geb., 16:1\u201321, 1970.","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5:246\u2013258, 1971.","journal-title":"Mathematical Systems Theory"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, 218, 1971.","DOI":"10.1007\/BFb0112458"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr. Process complexity and effective random tests. Journal of Computer and System Sciences, 7:376\u2013388, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR24","first-page":"656","volume":"35","author":"V. G. Vovk","year":"1987","unstructured":"V. G. Vovk. On a randomness criterion. Soviet Mathematics Doklady, 35:656\u2013660, 1987.","journal-title":"Soviet Mathematics Doklady"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T02:56:11Z","timestamp":1737341771000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_6"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}