Constructive dimension and Turing degrees, Theory Comput. Syst, vol.45, issue.4, pp.740-755, 2009. ,
Increasing Kolmogorov complexity, Electronic Colloquium on Computational Complexity, 2004. ,
, Covering codes, vol.54, 1997.
Algorithmic randomness and complexity. Theory and Applications of Computability, 2010. ,
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. ,
A short proof for a theorem of Harper about Hamming-spheres, Discrete Mathematics, vol.34, pp.311-313, 1981. ,
Extracting Kolmogorov complexity with applications to dimension zero-one laws, Inform. and Comput, vol.209, issue.4, pp.627-636, 2011. ,
Every sequence is reducible to a random one, Inform. and Control, vol.70, issue.2-3, pp.186-192, 1986. ,
Diagonally non-recursive functions and effective Hausdorff dimension, Bull. Lond. Math. Soc, vol.43, issue.4, pp.636-654, 2011. ,
Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory, vol.1, pp.385-393, 1966. ,
Generic computability, Turing degrees, and asymptotic density, J. Lond. Math. Soc, vol.85, issue.2, pp.472-490, 2012. ,
On the notion of a random sequence, Soviet Math. Dokl, vol.14, issue.5, pp.1413-1416, 1973. ,
Gales and the constructive dimension of individual sequences, Automata, languages and programming, vol.1853, pp.902-913, 2000. ,
An introduction to Kolmogorov complexity and its applications. Texts and Monographs in Computer Science, 1993. ,
Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math, vol.226, issue.1, pp.373-384, 2011. ,
The definition of random sequences, Information and Control, vol.9, pp.602-619, 1966. ,
On the construction of effectively random sets, J. Symbolic Logic, vol.69, issue.3, pp.862-878, 2004. ,
The theory of error-correcting codes. I, vol.16, 1977. ,
A unified approach to the definition of random sequences, Mathematical Systems Theory, vol.5, issue.3, pp.246-258, 1971. ,
The process complexity and effective random tests, Proceedings of the 4th STOC, pp.168-176, 1972. ,
Process complexity and effective random tests, Fourth Annual ACM Symposium on the Theory of Computing (Denver, vol.7, pp.376-388, 1972. ,
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
Kolmogorov complexity and algorithmic randomness (Russian title: Kolmogorovskaya slozhnost i algoritmichskaya sluchainost), 2013. ,
Algorithmic statistics: forty years later ,
URL : https://hal.archives-ouvertes.fr/hal-01480627
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
Montpellier, France. Supported by RaCAF ANR grant. E-mail address: alexander.shen@lirmm, vol.161 ,