Optimal bounds for single-source Kolmogorov extractors
HTML articles powered by AMS MathViewer
- by Laurent Bienvenu, Barbara F. Csima and Matthew Harrison-Trainor PDF
- Trans. Amer. Math. Soc. 373 (2020), 1983-2006 Request permission
Abstract:
The rate of randomness (or dimension) of a string $\sigma$ is the ratio $C(\sigma )/|\sigma |$ where $C(\sigma )$ is the Kolmogorov complexity of $\sigma$. While it is known that a single computable transformation cannot increase the rate of randomness of all sequences, Fortnow, Hitchcock, Pavan, Vinodchandran, and Wang showed that for any $0<\alpha <\beta <1$, there are a finite number of computable transformations such that any string of rate at least $\alpha$ is turned into a string of rate at least $\beta$ by one of these transformations. However, their proof only gives very loose bounds on the correspondence between the number of transformations and the increase of rate of randomness one can achieve. By translating this problem to combinatorics on (hyper)graphs, we provide a tight bound, namely: Using $k$ transformations, one can get an increase from rate $\alpha$ to any rate $\beta < k\alpha /(1+(k-1)\alpha )$, and this is optimal.References
- Laurent Bienvenu, David Doty, and Frank Stephan, Constructive dimension and Turing degrees, Theory Comput. Syst. 45 (2009), no. 4, 740–755. MR 2529744, DOI 10.1007/s00224-009-9170-1
- Boaz Barak, Russell Impagliazzo, and Avi Wigderson, Extracting randomness using few independent sources, SIAM J. Comput. 36 (2006), no. 4, 1095–1118. MR 2272272, DOI 10.1137/S0097539705447141
- Fan R. K. Chung, Constructing random-like graphs, Probabilistic combinatorics and its applications (San Francisco, CA, 1991) Proc. Sympos. Appl. Math., vol. 44, Amer. Math. Soc., Providence, RI, 1991, pp. 21–55. MR 1141922, DOI 10.1090/psapm/044/1141922
- Chris J. Conidis, A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, J. Symbolic Logic 77 (2012), no. 2, 447–474. MR 2963016, DOI 10.2178/jsl/1333566632
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, and Fengming Wang, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 4051, Springer, Berlin, 2006, pp. 335–345. MR 2305538, DOI 10.1007/11786986_{3}0
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 3rd ed., Texts in Computer Science, Springer, New York, 2008. MR 2494387, DOI 10.1007/978-0-387-49820-1
- Joseph S. Miller, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math. 226 (2011), no. 1, 373–384. MR 2735764, DOI 10.1016/j.aim.2010.06.024
- Michael Mitzenmacher and Eli Upfal, Probability and computing, 2nd ed., Cambridge University Press, Cambridge, 2017. Randomization and probabilistic techniques in algorithms and data analysis. MR 3674428
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- Jan Reimann. Computability and fractal dimension. PhD thesis, Universität Heidelberg, 2004.
- Andrew Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307–331. MR 930498
- Andrew Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173–195. MR 905280
- Nikolai K. Vereshchagin and Michael V. Vyugin, Independent minimum length programs to translate between given strings, Theoret. Comput. Sci. 271 (2002), no. 1-2, 131–143. Kolmogorov complexity. MR 1872286, DOI 10.1016/S0304-3975(01)00036-6
- Marius Zimand. Possibilities and impossibilities in Kolmogorov complexity extraction, SIGACT News, Dec 2010.
- Marius Zimand, Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors, 26th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 148–156. MR 3025369
Additional Information
- Laurent Bienvenu
- Affiliation: LaBRI, CNRS and Université de Bordeaux, France
- MR Author ID: 798548
- Barbara F. Csima
- Affiliation: Department of Pure Mathematics, University of Waterloo, Canada
- MR Author ID: 735103
- Matthew Harrison-Trainor
- Affiliation: School of Mathematics and Statistics, Victoria University of Wellington, New Zealand
- MR Author ID: 977639
- Received by editor(s): May 25, 2018
- Received by editor(s) in revised form: July 16, 2019
- Published electronically: November 12, 2019
- Additional Notes: The first author was supported by ANR-15-CE40-0016-01 RaCAF grant
The second author was partially supported by Canadian NSERC Discovery Grant 312501
The third author was supported by a Canadian NSERC Banting fellowship - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 373 (2020), 1983-2006
- MSC (2010): Primary 03032; Secondary 05C80
- DOI: https://doi.org/10.1090/tran/7972
- MathSciNet review: 4068287