{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T13:22:30Z","timestamp":1725974550575},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T00:00:00Z","timestamp":1301356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00224-011-9321-z","type":"journal-article","created":{"date-parts":[[2011,3,28]],"date-time":"2011-03-28T02:36:05Z","timestamp":1301279765000},"page":"227-245","source":"Crossref","is-referenced-by-count":11,"title":["Variations on Muchnik\u2019s Conditional Complexity Theorem"],"prefix":"10.1007","volume":"49","author":[{"given":"Daniil","family":"Musatov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Romashchenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,29]]},"reference":[{"issue":"1\u20132","key":"9321_CR1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0304-3975(01)00033-0","volume":"271","author":"An.A. Muchnik","year":"2002","unstructured":"Muchnik, An.A.: Conditional complexity and codes. Theor. Comput. Sci. 271(1\u20132), 97\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9321_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2 edn. Springer, Berlin (1997)","edition":"2"},{"key":"9321_CR3","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1109\/TIT.1973.1055037","volume":"19","author":"D. Slepian","year":"1973","unstructured":"Slepian, D., Wolf, J.K.: Noiseless coding of correlated information sources. IEEE Trans. Inf. Theory 19, 471\u2013480 (1973)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9321_CR4","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1137\/S009753979834388X","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Fortnow, L., Laplante, S.: Resource bounded Kolmogorov complexity revisited. SIAM J. Comput. 31(3), 887\u2013905 (2002)","journal-title":"SIAM J. Comput."},{"key":"9321_CR5","unstructured":"Musatov, D.: Extractors and an effective variant of Muchnik\u2019s theorem. Diplom (Master thesis). Faculty of mechanics and mathematics, MSU, 2006. http:\/\/arxiv.org\/abs\/0811.3958 (in Russian)"},{"issue":"1","key":"9321_CR6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/S0895480197329508","volume":"13","author":"J. Radhakrishnan","year":"2000","unstructured":"Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math. 13(1), 2\u201324 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"9321_CR7","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1137\/S0097539703431032","volume":"35","author":"O. Reingold","year":"2006","unstructured":"Reingold, O., Shaltiel, R., Wigderson, A.: Extracting randomness via repeated condensing. SIAM J. Comput. 35(5), 1185\u20131209 (2006)","journal-title":"SIAM J. Comput."},{"key":"9321_CR8","first-page":"228","volume-title":"Proc. of the 15th IEEE Conference on Computational Complexity, IEEE","author":"H. Buhrman","year":"2004","unstructured":"Buhrman, H., Lee, T., van Melkebeek, D.: Language compression and pseudorandom generators. In: Proc. of the 15th IEEE Conference on Computational Complexity, IEEE, pp. 228\u2013255 (2004)"},{"key":"9321_CR9","first-page":"141","volume-title":"Proc. 31 Annual ACM Symposium on Theory of Computing","author":"L. Trevisan","year":"1999","unstructured":"Trevisan, L.: Construction of extractors using pseudo-random generators. In: Proc. 31 Annual ACM Symposium on Theory of Computing, pp. 141\u2013148 (1999)"},{"key":"9321_CR10","doi-asserted-by":"crossref","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, 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9321_CR11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of Reed Solomon codes beyond the error-correcting bound. J. Complex. 13(1), 180\u2013193 (1997)","journal-title":"J. Complex."},{"key":"9321_CR12","volume-title":"ECCC TR95-056","author":"O. Goldreich","year":"1995","unstructured":"Goldreich, O.: Three XOR-Lemmas\u2014An Exposition. In: ECCC TR95-056 (1995)"},{"key":"9321_CR13","first-page":"330","volume-title":"Proc. of the 15th Annual ACM Symposium on Theory of Computing","author":"M. Sipser","year":"1983","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proc. of the 15th Annual ACM Symposium on Theory of Computing, pp. 330\u2013335 (1983)"},{"key":"9321_CR14","volume-title":"Dagstuhl Seminar Proceedings 06051","author":"A. Shen","year":"2011","unstructured":"Shen, A.: Combinatorial proof of Muchnik\u2019s theorem, Kolmogorov complexity and applications. In: Hutter, M., Merkle, W., Vitanyi, P. (eds.) Dagstuhl Seminar Proceedings 06051 (2011). ISSN1862\u20134405, http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2006\/625"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9321-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9321-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9321-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:22Z","timestamp":1558684462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9321-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,29]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9321"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9321-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,29]]}}}