{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:01:53Z","timestamp":1725562913365},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_61","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"701-712","source":"Crossref","is-referenced-by-count":4,"title":["Impossibility of Independence Amplification in Kolmogorov Complexity Theory"],"prefix":"10.1007","author":[{"given":"Marius","family":"Zimand","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"61_CR1","doi-asserted-by":"crossref","unstructured":"Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 384\u2013393 (2004)","DOI":"10.1109\/FOCS.2004.29"},{"key":"61_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. In: Proceedings of the 37th ACM Symposium on Theory of Computing, pp. 1\u201310 (2005)","DOI":"10.1145\/1060590.1060592"},{"issue":"4","key":"61_CR3","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1007\/s00224-009-9170-1","volume":"45","author":"L. Bienvenu","year":"2009","unstructured":"Bienvenu, L., Doty, D., Stephan, F.: Constructive dimension and Turing degrees. Theory Comput. Syst.\u00a045(4), 740\u2013755 (2009)","journal-title":"Theory Comput. Syst."},{"key":"61_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S1793042105000108","volume":"1","author":"J. Bourgain","year":"2005","unstructured":"Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory\u00a01, 1\u201332 (2005)","journal-title":"International Journal of Number Theory"},{"key":"61_CR5","unstructured":"Calude, C.: Information and Randomness: An Algorithmic Perspective, 2nd edn. Springer, Heidelberg (2002); 1st edn. (1994)"},{"key":"61_CR6","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing\u00a017, 230\u2013261 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"61_CR7","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Elbaz, A., Oliveira, R., Raz, R.: Improved randomness extraction from two independent sources. In: APPROX-RANDOM, pp. 334\u2013344 (2004)","DOI":"10.1007\/978-3-540-27821-4_30"},{"key":"61_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1007\/978-3-540-45198-3_22","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Y. Dodis","year":"2003","unstructured":"Dodis, Y., Oliveira, R.: On extracting private randomness over a public channel. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 252\u2013263. Springer, Heidelberg (2003)"},{"key":"61_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic randomness and complexity","author":"R. Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic randomness and complexity. Springer, Heidelberg (2010)"},{"key":"61_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/11786986_30","volume-title":"Automata, Languages and Programming","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Hitchcock, J., Pavan, A., Vinodchandran, N., Wang, F.: Extracting Kolmogorov complexity with applications to dimension zero-one laws. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 335\u2013345. Springer, Heidelberg (2006)"},{"key":"61_CR11","unstructured":"Hitchcock, J., Pavan, A., Vinodchandran, N.: Kolmogorov complexity in randomness extraction. In: Electronic Colloquium on Computational Complexity (ECCC) (09-071) (2009)"},{"key":"61_CR12","doi-asserted-by":"crossref","unstructured":"Li, M., Vitanyi, P.: An introduction to Kolmogorov complexity and its applications, 3rd edn. Springer, Heidelberg (2008); 1st edn. (1993)","DOI":"10.1007\/978-0-387-49820-1"},{"key":"61_CR13","unstructured":"Miller, J.: Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics (2008) (to appear)"},{"key":"61_CR14","unstructured":"Nies, A., Reimann, J.: A lower cone in the wtt degrees of non-integral effective dimension. In: Proceedings of IMS workshop on Computational Prospects of Infinity, Singapore (2006) (to appear)"},{"key":"61_CR15","doi-asserted-by":"crossref","unstructured":"Rao, A.: Extractors for a constant number of polynomially small min-entropy independent sources. In: Proceedings of the 38th ACM Symposium on Theory of Computing, pp. 497\u2013506 (2006)","DOI":"10.1145\/1132516.1132589"},{"key":"61_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/978-3-540-85363-3_44","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Rao","year":"2008","unstructured":"Rao, A., Zuckerman, D.: Extractors for three uneven-length sources. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 557\u2013570. Springer, Heidelberg (2008)"},{"key":"61_CR17","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1060590.1060593","volume-title":"STOC","author":"R. Raz","year":"2005","unstructured":"Raz, R.: Extractors with weak random seeds. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 11\u201320. ACM, New York (2005)"},{"key":"61_CR18","unstructured":"Reimann, J.: Computability and fractal dimension. Tech. rep., Universit\u00e4t Heidelberg (2004) (ph.D. thesis)"},{"key":"61_CR19","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. Santha","year":"1986","unstructured":"Santha, M., Vazirani, U.: Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences\u00a033, 75\u201387 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"61_CR20","unstructured":"Shen, A.: Algorithmic information theory and Kolmogorov complexity. Tech. Rep. 2000-034, Uppsala Universitet (December 2000)"},{"key":"61_CR21","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pp. 32\u201342 (2000)","DOI":"10.1109\/SFCS.2000.892063"},{"issue":"1-2","key":"61_CR22","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(01)00036-6","volume":"271","author":"N.K. Vereshchagin","year":"2002","unstructured":"Vereshchagin, N.K., Vyugin, M.V.: Independent minimum length programs to translate between given strings. Theor. Comput. Sci.\u00a0271(1-2), 131\u2013143 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"61_CR23","unstructured":"Zimand, M.: Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence. In: Proceedings 26th STACS, Freiburg, Germany, February 26-29 (2009)"},{"key":"61_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/978-3-540-79709-8_33","volume-title":"CSR 2008","author":"M. Zimand","year":"2008","unstructured":"Zimand, M.: Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol.\u00a05010, pp. 326\u2013338. Springer, Heidelberg (2008)"},{"key":"61_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/978-3-642-03073-4_51","volume-title":"CiE","author":"M. Zimand","year":"2009","unstructured":"Zimand, M.: On generating independent random strings. In: Ambos-Spies, K., L\u00f6we, B., Merkle, W. (eds.) CiE. LNCS, vol.\u00a05635, pp. 499\u2013508. Springer, Heidelberg (2009)"},{"issue":"6","key":"61_CR26","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"A. Zvonkin","year":"1970","unstructured":"Zvonkin, A., Levin, L.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys\u00a025(6), 83\u2013124 (1970)","journal-title":"Russian Mathematical Surveys"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T20:49:24Z","timestamp":1685738964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}