{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:19Z","timestamp":1725483739244},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_29","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"333-342","source":"Crossref","is-referenced-by-count":4,"title":["On the Autoreducibility of Random Sequences"],"prefix":"10.1007","author":[{"given":"Todd","family":"Ebert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"29_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon N., Spencer J. The Probabilistic Method. John Wiley and Sons, New York, 1992."},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"Bennett C., Gill J. Relative to a Random Oracle A, P A \u2260 NP A \u2260 co NP A With Probability 1. SIAM Journal on Computing, 10, 96\u2013113, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR3","volume-title":"Theory and Practice of Error Control Codes","author":"R. Blahut","year":"1984","unstructured":"Blahut R. Theory and Practice of Error Control Codes. Addison Wesley, Reading, Ma, 1984."},{"issue":"6","key":"29_CR4","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1137\/S0097539793238140","volume":"23","author":"R. Book","year":"1984","unstructured":"Book R. On Languages Reducible to Algorithmically Random Languages. SIAM Journal on Computing, Vol. 23, No. 6, 1275\u20131282, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01578842","volume":"27","author":"R. Book","year":"1994","unstructured":"Book R., Lutz J., Wagner K. W. An Observation on Probability Versus Randomness. Math. Systems Theory, 27, 201\u2013209, 1994.","journal-title":"Math. Systems Theory"},{"key":"29_CR6","volume-title":"Introductory Combinatorics","author":"R. Brualdi","year":"1988","unstructured":"Brualdi R. Introductory Combinatorics. North-Holland, NY, 1988."},{"doi-asserted-by":"crossref","unstructured":"Buhrman H., van Melkebeek D., Regan K.W., Sivakumar D., Strauss M., A generalization of resource-bounded measure, with an application to the BPP vs. EXP problem. Manuscript, 1999. Preliminary versiond appeared in Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 161\u2013171, 1998, and as University of Chicago, Department of Computer Science, Technical Report TR-97-04, May 1997.","key":"29_CR7","DOI":"10.1007\/BFb0028558"},{"unstructured":"Cutland N. Introduction to Computability. Cambridge Univ. Press, 1992.","key":"29_CR8"},{"unstructured":"Ebert T. Applications of Recursive Operators to Randomness and Complexity. Ph.D. Thesis, University of California at Santa Barbara, 1998.","key":"29_CR9"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(86)80004-3","volume":"70","author":"P. G\u00e1cs","year":"1986","unstructured":"G\u00e1cs P. Every Sequence is Reducible to a Random One. Information and Control, 70, 186\u2013192, 1986.","journal-title":"Information and Control"},{"key":"29_CR11","volume-title":"Applied Abstract Algebra","author":"K.H. Kim","year":"1983","unstructured":"Kim K.H., Roush F.W. Applied Abstract Algebra. John Wiley and Sons, New York, 1983."},{"key":"29_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1993","unstructured":"Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York, 1993."},{"unstructured":"Lutz J. K\u00f6nig\u2019s Lemma, Randomness, and the Arithmetical Hierarchy. Unpublished Lecture Notes, Iowa St. Univ., 1993.","key":"29_CR13"},{"issue":"5","key":"29_CR14","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/0222065","volume":"22","author":"J. Lutz","year":"1993","unstructured":"Lutz J. A Pseudorandom Oracle Characterization of BPP. SIAM Journal on Computing, 22(5):1075\u20131086, 1993.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Lutz J. The Quantitative Structure of Exponential Time. In: Hemaspaandra L., Selman A., editors, Complexity Theory Restropsective II, Springer Verlag, 1997, 225\u2013260.","key":"29_CR15","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"29_CR16","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. On the Definition of Random Sequences. Information and Control, 9, 602\u2013619, 1966.","journal-title":"Information and Control"},{"unstructured":"Wolfgang Merkle. Personal communication, December 1999.","key":"29_CR17"},{"key":"29_CR18","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1992","unstructured":"Rogers H. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, 1992."},{"key":"29_CR19","volume-title":"Probability","author":"A.N. Shiryaev","year":"1995","unstructured":"Shiryaev A.N. Probability. Springer-Verlag, New York, 1995."},{"key":"29_CR20","first-page":"814","volume":"11","author":"B.A. Trakhtenbrot","year":"1970","unstructured":"Trakhtenbrot, B.A. On Autoreducibility. Soviet Math dokl., 11:814\u2013817, 1970.","journal-title":"Soviet Math dokl."},{"key":"29_CR21","volume-title":"Computational Complexity","author":"K. W. Wagner","year":"1986","unstructured":"Wagner K. W., Wechsung G. Computational Complexity. Deutscher Verlag der Wissenschaften, Berlin, 1986."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T18:41:27Z","timestamp":1556390487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}