L. Bienvenu, D. Doty, and F. Stephan, Constructive dimension and Turing degrees, Theory Comput. Syst, vol.45, issue.4, pp.740-755, 2009.

H. Buhrman, L. Fortnow, I. Newman, and N. Vereshchagin, Increasing Kolmogorov complexity, Electronic Colloquium on Computational Complexity, 2004.

G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering codes, vol.54, 1997.

G. Rodney, D. R. Downey, and . Hirschfeldt, Algorithmic randomness and complexity. Theory and Applications of Computability, 2010.

P. Delsarte and P. Piret, Do most binary linear codes achieve the Goblick bound on the covering radius?, IEEE Trans. Inform. Theory, vol.32, issue.6, pp.826-828, 1986.

P. Frankl and Z. Füredi, A short proof for a theorem of Harper about Hamming-spheres, Discrete Mathematics, vol.34, pp.311-313, 1981.

. Fhp`fhp`11]-lance, J. M. Fortnow, A. Hitchcock, N. V. Pavan, F. Vinodchandran et al., Extracting Kolmogorov complexity with applications to dimension zero-one laws, Inform. and Comput, vol.209, issue.4, pp.627-636, 2011.

P. Gács, Every sequence is reducible to a random one, Inform. and Control, vol.70, issue.2-3, pp.186-192, 1986.

N. Greenberg and J. S. Miller, Diagonally non-recursive functions and effective Hausdorff dimension, Bull. Lond. Math. Soc, vol.43, issue.4, pp.636-654, 2011.

L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory, vol.1, pp.385-393, 1966.

C. G. Jockusch, J. , and P. E. Schupp, Generic computability, Turing degrees, and asymptotic density, J. Lond. Math. Soc, vol.85, issue.2, pp.472-490, 2012.

L. A. Levin, On the notion of a random sequence, Soviet Math. Dokl, vol.14, issue.5, pp.1413-1416, 1973.

H. Jack and . Lutz, Gales and the constructive dimension of individual sequences, Automata, languages and programming, vol.1853, pp.902-913, 2000.

M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications. Texts and Monographs in Computer Science, 1993.

J. S. Miller, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math, vol.226, issue.1, pp.373-384, 2011.

P. Martin-löf, The definition of random sequences, Information and Control, vol.9, pp.602-619, 1966.

W. Merkle and N. Mihailovi?, On the construction of effectively random sets, J. Symbolic Logic, vol.69, issue.3, pp.862-878, 2004.

F. J. Macwilliams and N. J. Sloane, The theory of error-correcting codes. I, vol.16, 1977.

C. Peter-schnorr, A unified approach to the definition of random sequences, Mathematical Systems Theory, vol.5, issue.3, pp.246-258, 1971.

C. Peter-schnorr, The process complexity and effective random tests, Proceedings of the 4th STOC, pp.168-176, 1972.

C. Schnorr, Process complexity and effective random tests, Fourth Annual ACM Symposium on the Theory of Computing (Denver, vol.7, pp.376-388, 1972.

A. Shen, Around Kolmogorov complexity: Basic Notions and Results, Measures of Complexity. Festschrift for Alexey Chervonenkis, pp.75-116, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01233758

V. A. Uspensky, N. K. Vereshchagin, and A. Shen, Kolmogorov complexity and algorithmic randomness (Russian title: Kolmogorovskaya slozhnost i algoritmichskaya sluchainost), 2013.

N. Vereshchagin and A. Shen, Algorithmic statistics: forty years later
URL : https://hal.archives-ouvertes.fr/hal-01480627

N. K. Vereshchagin, M. B. Paul, and . Vitányi, Rate distortion and denoising of individual data using Kolmogorov complexity, IEEE Trans. Inform. Theory, vol.56, issue.7, pp.3438-3454, 2010.

, E-mail address: greenberg@msor.vuw.ac.nz URL, p.480

L. Dr and . Madison, Montpellier, France. Supported by RaCAF ANR grant. E-mail address: alexander.shen@lirmm, vol.161