, \B\ ^ c/(n + 1), and it suffices to cover A by at most poly(n)|A|/|F?| balls of radius b. Cover all the strings that are at distance at most b from the center of A by one ball of radius b that has the same center as A. Partition the remaining points into spheres of radii d -b + 1,..., a: the sphere of radius d consists of all strings at Hamming distance exactly d from the center of A. As the number of those spheres is at most n, it suffices, for every d ? (b, n/2], to cover a sphere of radius d by at most poly(n)|S'|/|H| balls of radius b. Fix d and a sphere S of radius d 6 (b

A. Kolmogorov and V. Uspensky-;-s-i-a-m-j, Translated with annoying errors (for instance, everywhere instead of the correct translation "recursively enumerable" an incorrect translation "countable" is used); better translation can be, vol.32, pp.389-412

V. Uspensky and A. Semenov, A lg o r ith m s, vol.269, p.pp, 1993.

V. Uspensky, A. Semenov, and A. Shen, Can an individual sequence of zeros and ones be ran dom?" R u s s ia n M a th, pp.121-189, 1990.

V. Uspensky and A. Shen, Relations between varieties of Kolmogorov complexities, vol.29, pp.271-292, 1996.

A. Muchnik, A. Semenov, and V. Uspensky, Mathematical metaphysics of randomness, vol.207, pp.263-317, 1998.

A. Shen, On relations between different algorithmic definitions of randomness, vol.38, pp.316-319, 1989.

R. Ahlswede, N. Cai, S. R. Li, R. Yeung, and . ;-i-e-e-e-t, Network Information Flow, vol.46, pp.1204-1216, 2000.

R. Ahlswede and J. Körner, On common information and related characteristics of correlated in formation sources, Preprint, Presented at the 7th Prague Conference on Information Theory, 1974.

N. Alon, I. Newman, A. Shen, G. Tardos, and N. Vereshchagin, Partitioning multi-dimensional sets in a small number of, vol.28, pp.5-095, 2005.

M. Andreev, B. Beavers, and K. Complexity, , pp.195-204, 2016.

B. Bauwens, Plain and prefix complexity characterizations of 2-randomness: simple proofs, vol.54, pp.615-629, 2013.

B. Bauwens and A. Shen, Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity, vol.79, pp.620-632, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-00853082

B. Bauwens, A. Shen, and H. Takahashi, , 2016.

V. Becher, S. Figueira, and P. R. , Turing unpublished algorithm for normal numbers, vol.377, pp.126-138, 2007.

C. H. Bennett, P. Gåcs, M. Li, P. M. Vitånyi, and Z. W. , Preliminary version, Thermo dynamics of computation and information distance, P r o c . 2 5 th A C M S y m p, vol.44, pp.21-30, 1993.

L. Bienvenu, G a m e -st i c i t, 2008.

L. Bienvenu, D. Desfontaines, and A. Shen, Generic algorithms for halting problem and optimal machines revisited, v, vol.12, pp.1-29, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-01233778

L. Bienvenu, R. Downey, K. Complexity, . Solovay-functions, and . Le-c-tr-o-n-ic-p-r-o-c, 6 th S y m p, vol.2, p.2009, 2009.

L. Bienvenu, P. Gåcs, M. Hoyrup, C. Rojas, and A. Shen, Algorithmic tests and randomness with respect to a class of measures, P r o c, vol.274, pp.41-102, 2011.

L. Bienvenu, R. Hölzl, C. Porter, and P. Shafer, Randomness and semi-measures

L. Bienvenu, M. Hoyrup, and A. Shen,

L. Bienvenu, . Muchnik-an, A. Shen, and N. K. Vereshchagin, Limit complexities revisited, T h e o r y o f C o m p u tin g S y s te m s , v, vol.47, pp.720-736, 2010.

L. Bienvenu and . Sablikm, The dynamics of cellular automata in shift-invariant topologies, Lecture Notes in Computer Science, v, vol.1, pp.84-95, 2007.

L. Bienvenu, G. Shafer, and A. Shen, On the history of martingales in the study of random ness, E le c tr o n ic J o u r n a l f o r H is to r y o f P r o b a b ility a n d S t a t i s t i c s, p.491, 2009.

L. Bienvenu and A. Shen, Algorithmic information theory and martingales

L. Bienvenu and A. Shen, Random semicomputable reals revisited, Lecture Notes in Computer Science, pp.31-45, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00845796

L. Bienvenu, A. Shen, ?. K-trivial, and M. Sequences, Lecture Notes in Computer Science, vol.9300, pp.1-23, 2015.

E. Borei, L e h a s a r d, 1920.

E. Borei, English translation: Borei E, 1961.

H. Buhrman, L. Fortnow, S. Laplante, and S. Resource-bounded-kolmogorov-complexity-revisited, , pp.887-905, 2002.

H. Buhrman, L. Fortnow, I. Newman, and N. Vereshchagin, Increasing Kolmogorov complexity, P r o c . 2 2 n d S y m p, STACS 2005), vol.3404, pp.4-081, 2004.

C. S. Calude, , pp.450-453, 1994.

C. S. Calude, P. Hertling, B. Khoussainov, and Y. Wang, Recursively enumerable reals and Chaitin Omega numbers, P r o c . 1 5 th S y m p, Lecture Notes in Computer Science v, vol.1373, pp.596-606, 1998.

C. S. Calude, L. Staiger, and S. Terwijn, On partial randomness, pp.20-30, 2006.

G. J. Chaitin, On the length of programs for computing binary sequences, vol.13, pp.547-569, 1966.

G. J. Chaitin, On the length of programs for computing binary sequences: statistical con siderations, vol.16, pp.145-159, 1969.

G. J. Chaitin and . ;-a-c-m-s-i-g-a-c-t-n-e-w-s, Computational complexity and GödePs incompleteness theorem, pp.11-12, 1971.

G. J. Chaitin, Information-theoretic limitations of formal systems, vol.21, pp.403-424, 1974.

G. J. Chaitin, A theory of program size formally identical to information theory, vol.22, pp.329-340, 1975.

G. J. Chaitin, Information-theoretic characterizations of recursive infinite strings, vol.1, pp.45-48, 1976.

G. J. Chaitin, Incompleteness theorems for random reals, A d v tic s , v, vol.8, pp.119-146, 1987.

G. J. Chaitin, A lg o r ith m ic i n f o r m a tio n th e o r y, 1987.

D. G. Champernowne, The construction of decimals normal in the scale of ten, pp.254-260, 1933.

T. H. Chan, R. W. Yeung, and . ;-i-e-e-e-t, On a relation between information inequalities and group theory, vol.48, 1992.

A. V. Chernov, Complexity of sets obtained as values of propositional formulas, pp.131-139, 2004.

A. Chernov, . A. Muchnik-an, A. Romashchenko, A. Shen, and N. K. Vereshchagin, Upper semi lattice of binary strings with the relation "x is simple conditional to, pp.114-122, 1999.

A. Chernov, M. Hutter, and J. Schmidhuber, Algorithmic complexity bounds on future prediction errors, p.205, 2007.

A. Chernov, A. Shen, N. Vereshchagin, and V. Vovk, On-line Probability, Complexity and Ran domness, P r o c, pp.138-153, 2008.

A. Chernov, D. Skvortsov, E. Skvortsova, and N. Vereshchagin, Variants of realizability for propositional formulas and the logic of the weak law of excluded middle, P r o c . o f S te k lo v I n s t i t, pp.74-88, 2002.

F. R. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some intersection theorems for ordered sets and graphs, vol.43, pp.23-37, 1986.

A. Church, On the concept of a random sequence, vol.46, pp.130-135, 1940.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, A lg o r ith m s, 2009.

R. P. Daley, Minimal-program complexity of pseudo-recursive and pseudo-random sequences, M a th e m a tic a l S y s t e m s T h e o r y (now T h e o r y o f C o m p u tin g S y s t e m s ), pp.83-94, 1975.

A. P. Dawid, S. De-rooij, G. Shafer, A. Shen, N. K. Vereshchagin et al., Insur ing against loss of evidence in game-theoretic probability, S t a t i s t i c s & P r o b a b ility L e tte r s , v, vol.81, pp.157-162, 2011.

A. Day, Increasing the gap between descriptional complexity and algorithmic probability, P r o c . 2 4 th I E E E C, pp.263-273, 2009.

R. Downey, D. Hirschfeldt, and . Ity, , pp.855-978, 2010.

R. Downey, D. Hirschfeldt, A. Nies, and . Terwijns, Calibrating randomness., T h e B u lle tin o f S y m b o lic L o g ic, pp.411-491, 2006.

B. Durand, L. Levin, A. Shen, and . Complex-tilings, , vol.73, pp.593-613, 2007.

D. Durand, A. Shen, and N. Vereshchagin, Descriptive complexity of computable sequences, Lecture Notes in Computer Science v. 1563, vol.171, pp.1-087, 1999.

B. Durand and N. Vereshchagin, Kolmogorov-Loveland stochasticity for finite strings, I n f o r m a t i o n P r o c e s s in g L e tte r s , v, vol.91, pp.263-269, 2004.

L. Fortnow, T. Lee, and N. Vereshchagin, Kolmogorov complexity with error, Lecture Notes in Computer Science v, vol.3884, pp.4-080, 2004.

P. Gâcs, On the symmetry of algorithmic information, vol.15, pp.1477-1480, 1974.

P. Gâcs, Exact expressions for some randomness test, vol.26, pp.385-394, 1980.

P. Gâcs, Preliminary version, P r o c . 2 2 n d S y m p, On the relation between descriptional complexity and algorithmic probability, vol.22, pp.296-303, 1981.

P. Gâcs, Every sequence is reducible to a random one, pp.186-192, 1986.

P. Gâcs and J. Körner, Common information is far less than mutual information, pp.149-162, 1973.

P. Gâcs, J. Tromp, and P. M. Vitånyi, Algorithmic statistics, I E E r, vol.47, pp.2443-2463, 2001.

O. Goldreich, , 2007.

K. Gorbunov and . Yu, , pp.383-386, 1998.

P. R. Halmos and N. Y. M-e-a-s-u-r-e-t-h-e-o-r-y, , vol.292, 1950.

D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, Inequalities for Shannon entropies and Kolmogorov complexities, vol.60, pp.13-23, 1997.

D. Hammer and A. Shen, A strange application of Kolmogorov complexity, S y s te m s, pp.1-4, 1998.

W. Hoeffding, Probability inequalities for sums of bounded random variables, vol.58, pp.13-30, 1963.

R. Hölzl, T. Kräling, and W. Merkle, Time-bounded Kolmogorov complexity and Solovay func tions, Lecture Notes in Computer Science v, vol.5734, pp.392-402, 2009.

M. Hutter, A lg o r ith m ic P r o b a b ility, vol.278, 2005.

R. Impagliazzo, R. Shaltiel, and W. A. , Extractors and pseudo-random generators with optimal seed length, pp.1-10, 2000.

S. Kakutani, On equivalence of infinite product measures, Second Series, v, vol.49, issue.1, pp.214-224, 1948.

E. Kalinina, Prefix-free and prefix-correct complexities with compound conditions, P ro c

, th C o m p u te r S c ie n c e S y m p . in R u s s ia, vol.6072, pp.259-265, 2010.

P. Karpovich, Monotone complexity of a pair, P r o c . s ia (CSR 2010), Lecture Notes in Computer Science v, vol.6072, pp.266-275

B. Kjos-hanssen, The probability distribution as a computational resource for randomness testing, 2010.

B. Kjos-hanssen, W. Merkle, F. Stephan, and . Kolmogorov, Pre liminary version, P r o c . 2 3 r d S y m p, Lecture Notes in Computer Science v, vol.363, pp.149-161, 2006.

S. C. Kleene, On the interpretation of intuitionistic number theory, pp.109-124, 1945.

A. Kolmogoroff, Zur Deutung der intuitionistishen Logik, M a th e m a tis c h e Z e its c h r if t, vol.35, pp.58-65, 1932.

A. N. Kolmogorov and . ;-s-s-,-s-e-r-.-a, On tables of random numbers, vol.25, pp.387-395, 1963.

A. N. Kolmogorov, Three approaches to the quantitative definition of information, P r o b le m s I n f o r m . T r a n s m is s io n, pp.1-7, 1965.

A. N. Kolmogorov, Logical basis for information theory and probability theory, I E E E T ra n s. I n f o r m . T h e o r, vol.14, pp.662-664, 1968.

A. N. Kolmogorov, Combinatorial foundations of information theory and the calculus of probabilities, pp.29-40, 1983.

A. N. Kolmogorov and S. V. Fomin, , vol.403, 1970.

A. N. Kolmogorov, Talk at the Information Theory Symposium in, 1974.

A. N. Kolmogorov, The definition of (a, /3)-stochasticity was given in this talk, and the question about the fraction of non-stochastic objects was asked, 1981.

A. N. Kolmogorov, V. A. Uspensky, . Algorithms, S. Randomness, and . I-a-m-j-.-t-h-e-o-r-y-p-ro-b-a-b, Without annoy ing translation errors, Probab. Theory and Appl, vol.32, issue.1, pp.3-55, 1987.

, A collection of papers, Voprosy istorii informatiki, 2001.

, Philosophy of Russian Academy of Sciences, pp.118-137, 1965.

A. Kucera, . Measure, and -. Il^, R e c u r s io n T h e o r y W e e k ( O b e r w o lfa c h , 1 9 8 4 ), pp.245-259, 1985.

A. Kucera, T. Slaman, R. Randomness, and S. Enumerability, , pp.199-211, 2001.

L. Kuipers and H. Niederreiter, , 1949.

M. Kummer, On the complexity of random strings, P r o c . u te r S c ie n c e (STACS 1996), vol.1046, pp.25-36

M. Van-lambalgen, , 1987.

K. De-leeuw, E. F. Moore, ?. E. Shannon, and N. Shapiro, Computability by probabilis tic machines, pp.183-212, 1956.

L. A. Levin, dissertation directed by A. N. Kolmogorov; turned down as required by the Soviet authorities despite unanimously positive reviews), pp.224-235, 1971.

L. A. Levin, On the notion of a random sequence, pp.1413-1416, 1973.

L. A. Levin, Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, P r o b le m s o f I n f o r m a tio n T r a n s m is s io n, pp.206-210, 1974.

L. A. Levin, Various measures of complexity for finite objects (axiomatic description, vol.17, pp.522-526, 1976.

L. A. Levin, On the principle of conservation of information in intuitionistic mathematics, vol.17, pp.601-605, 1976.

L. A. Levin, Uniform tests of randomness, vol.17, pp.337-340, 1976.

L. A. Levin, On a concrete method of assigning complexity measures, vol.18, pp.727-731, 1977.

L. A. Levin, A concept of independence with application in various fields of mathematics, vol.21, p.pp, 1980.

L. A. Levin, Randomness conservation inequalities: information and independence in math ematical theories, pp.15-37, 1984.

L. A. Levin and V. V. Vyugin, Invariant properties of informational bulks, P r o c . 6 th S y m p, Lecture Notes in Computer Science v, vol.153, pp.359-364, 1977.

L. A. Levin, Preliminary version, P r o c . 4 3 th I E E E S y m p, pp.761-768, 2002.

M. Li and P. Vitånyi, , vol.2, 1993.

S. R. Li, R. W. Yeung, and N. Cai, Linear network coding, pp.371-381, 2003.
URL : https://hal.archives-ouvertes.fr/hal-01327498

L. H. Loomis and H. Whitney, An inequality related to the isoperimetric inequality, vol.55, pp.961-962, 1949.

D. W. Loveland, A new interpretation of von Mises' concept of a random sequence, pp.279-294, 1966.

D. W. Loveland, The Kleene hierarchy classification of recursively random sequences, T ra n s. A m e r . M a th, vol.125, pp.497-510, 1966.

D. W. Loveland, A Variant of the Kolmogorov concept of complexity, pp.510-526, 1969.

D. W. Loveland, On minimal-program complexity measures, P r o c . 1 s t A C M S y m p, pp.61-65, 1969.

J. Lutz and . ;-s-i-a-m-j, Preliminary version, P r o c . 1 5 th I E E E C, Dimension in complexity classes, vol.32, pp.158-169, 2000.

J. H. Lutz, Preliminary version, Gales and the constructive dimension of individual sequences, Lecture Notes in Computer Science v, vol.187, issue.1, pp.902-913, 2000.

K. Makarychev and M. Yu-;-i-e-e-e-t, , vol.58, pp.5279-5286, 2012.

K. Makarychev, M. Yu, A. Romashchenko, and N. Vereshchagin, A new class of non-Shannon-type inequalities for entropies, S y s te m s, pp.147-166, 2002.

, Moscow: Sovetskoe radio (Soviet radio), p.128, 1980.

P. Martin-löf, The definition of random sequences, I ta tio n ), pp.602-619, 1966.

P. Martin-löf and . Algorithmen-und-zufällige-folgen, Vier Vorträge von Per Martin-Löf (Stockholm) gehalten am Mathematischen, p.61, 1966.

P. Martin-löf, Complexity oscillations in infinite binary sequences, pp.225-230, 1971.

E. Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimen sion, I n f o r m a tio n P r o c e s s in g L e tte r s , v, vol.84, pp.1-3, 2002.

W. Merkle, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, vol.68, pp.1362-1376, 2003.

, Lecture Notes in Computer Science v, vol.2380, pp.390-400, 2002.

W. Merkle, The complexity of stochastic sequences, P r o c . le x ity, pp.230-235, 2003.

J. Miller, Every 2-random real is Kolmogorov random, pp.907-913, 2004.

J. Miller, Contrasting plain and prefix-free Kolmogorov complexity, www.math. w ise

J. Miller and L. Yu, On initial segment complexity and degrees of randomness, vol.360, pp.3193-3210, 2008.

J. Miller, The ? -Degrees, low for ? degrees, and weakly low for ? sets, vol.50, pp.381-391, 2009.

J. Miller, Two notes on subshifts, pp.1617-1622, 2012.

R. Von-mises and . Grundlagen-der-wahrscheinlichkeitsrechnung, Z e its c h r if t, Bd, vol.5, pp.57-106, 1919.

R. Von-mises, , p.189, 1928.

R. Von-mises, S ta t i s t i c s , v, On the foundations of probability and statistics, vol.12, pp.340-355, 1941.

R. Von-mises and J. L. Doob, Discussion of papers on probability theory, vol.12, pp.356-359, 1941.

R. A. Moser, A constructive proof of the Lovasz Local Lemma, P r o c . 4 1 s t A C M S y m p, pp.343-350, 2009.

R. A. Moser and G. Tardos, A constructive proof of the general Lovasz Local Lemma, vol.57, 2010.

.. A. Muchnik-an, On the basic structures of the descriptive theory of algorithms, vol.32, pp.671-674, 1985.

.. A. Muchnik-an and . ;-s-i-a-m-t-h-e-o-r-y-p, Lower limits on frequencies in computable sequences and relativized a priori probability, pp.513-514, 1987.

.. A. Muchnik-an, On common information, vol.207, pp.319-328, 1998.

M. An, Preliminary version, Muchnik A., Semenov A., Multi-conditional descriptions and codes in Kolmogorov complexity, vol.271, pp.0-015, 2000.

.. A. Muchnik-an, I. Mezhirov, A. Shen, N. K. Vereshchagin, and . Le-x-ity, , 2010.

.. A. Muchnik-an and S. E. Positselsky, Kolmogorov entropy in the context of computability theory, pp.15-35, 2002.

.. A. Muchnik-an and A. Romashchenko, Stability of properties of Kolmogorov complexity under relativization. P r o b le m s o f I n f o r m a tio n T r a n s m is s io n, Lecture Notes in Computer Science v, vol.46, issue.1, pp.527-538, 2008.

.. A. Muchnik-an, A. L. Semenov, and V. A. Uspensky, Mathematical metaphysics of randomness, vol.207, pp.263-317, 1998.

.. A. Muchnik-an, A. Shen, M. Ustinov, N. K. Vereshchagin, M. Vyugin et al., Non-reducible descriptions for conditional Kolmogorov complexity, Non-reducible de scriptions for conditional Kolmogorov complexity, vol.384, pp.4-054, 2004.

.. A. Muchnik-an and N. K. Vereshchagin, Shannon entropy vs. Kolmogorov complexity

, R u s s ia, vol.3967, pp.281-291, 2006.

.. A. Muchnik-an and N. K. Vereshchagin, Preliminary versions, Much nik An. A., Vereshchagin N .K ., Logical operations and Kolmogorov complexity, vol.274, pp.90-104, 2011.

. Th-i-e-e-e-c, , pp.1-089, 2001.

D. Musatov, Improving the space-bounded version of Muchnik's conditional complexity theorem via "naive" derandomization, P r o c . 6 th C o m p u te r S c ie n c e S y m p . in R u s s ia, Lecture Notes in Computer Science v, vol.6651, pp.64-76, 2011.

D. Musatov, Space-bounded Kolmogorov extractors, P r o c . 7 th C o m p u te r S c ie n c e S y m p . in R u s s ia, vol.7353, pp.266-277, 2012.

D. Musatov, A. Romashchenko, and A. Shen, Variations on Muchnik's conditional complexity theorem, vol.49, pp.227-245, 2011.

, th C o m p u te r S c ie n c e S y m p . in R u s s ia, vol.5675, pp.250-262, 2009.

H. Niederreiter, A combinatorial problem for vector spaces over finite fields, D is c r e te M a th e m a tic s, pp.221-228, 1991.

A. Nies, , vol.420, 2009.

A. Nies, F. Stephan, and S. Terwijn, Randomness, relativization and Turing degrees, vol.70, pp.515-535, 2005.

G. Novikov, , 2016.

T. Rado, On non-computable functions, vol.3, pp.877-884, 1962.

I. Razenshteyn, Common information revisited, 2012.

J. Reimann,

A. Romashchenko, A. Rumyantsev, and A. Shen, , p.80, 2011.

A. Romashchenko and A. Shen, Topological arguments for Kolmogorov complexity, T h e o r y o f C o m p u tin g S y s te m s , v, vol.56, pp.513-526, 2015.

A. Romashchenko, A. Shen, and N. Vereshchagin, Preliminary versions, P r o c . 1 5 th I E E E C, Combinatorial interpretation of Kolmogorov complexity, vol.271, pp.0-026, 2000.

A. Rumyantsev and . Kolmogorov-complexity, Lovasz Local Lemma and critical exponents, P r o c . 2 n d C o m p u te r S c ie n c e S y m p . in R u s s ia, Lecture Notes in Computer Science v, vol.4649, pp.349-355, 2007.

A. Rumyantsev, Infinite computable version of Lovasz Local Lemma, 2010.

A. Rumyantsev, M. Ushakov, and . Forbidden-substrings, Kolmogorov complexity and almost periodic sequences, P r o c . 2 3 r d S y m p, Lecture Notes in Computer Science v, vol.3884, pp.396-407, 2006.

W. Schmidt, On normal numbers, pp.661-672, 1960.

?. P. Schnorr, Eine Bemerkung zum Begriff der zufälligen Folge, Z d V e rw . G e b ie te, vol.14, pp.27-35, 1969.

C. P. Schnorr, Uber die Definition effektiver Zufallstests, Teil I, Z d V e rw . G e b ie te, vol.15, pp.297-312, 1970.

?. P. Schnorr, Uber die Definition effektiver Zufallstests, Teil II, Z d V e rw . G e b ie te, vol.15, pp.313-328, 1970.

C. P. Schnorr, Klassifikation der Zufallsgesetze nach Komplexität und Ordnung, Z e its c h r if t f ü r W a h r s c h e in lic h k e its th e o r ie u n d V e rw . G e b ie te, vol.16, pp.1-21, 1970.

C. P. Schnorr, Lecture Notes in Mathematics, 1971.

?. P. Schnorr, A unified approach to the definition of random sequences, pp.246-258, 1971.

?. P. Schnorr and . Gödel-numberings,-p-r-o-c-.-i-f-i-p, , pp.56-58, 1971.

?. P. Schnorr, Process complexity and effective random tests, pp.168-176, 1973.

?. P. Schnorr, Optimal enumerations and optimal Gödel numberings, M a th e m a tic a l S y s te m s T h e o r y, pp.182-191, 1975.

G. Shafer, A. Shen, N. K. Vereshchagin, and V. Vovk, Test martingales, Bayes factors, and p-values, vol.26, pp.84-101, 2011.

G. Shafer, V. Vovk, and . York, , 2001.

A. Shen and . Aksiomaticheskoe, , pp.104-105, 1982.

A. Shen, The concept of (a,/3)-stochasticity in the Kolmogorov sense, and its properties, vol.28, pp.295-299, 1983.

A. Shen, On logical foundations of applications of probability theory

A. Shen, Algorithmic variants of the notion of entropy, vol.29, pp.569-573, 1984.

A. Shen, On relations between different algorithmic definitions of randomness, vol.38, pp.316-319, 1989.

A. Shen, Discussion on Kolmogorov Complexity and Statistical Analysis, vol.42, pp.340-342, 1999.

A. Shen, Multisource algorithmic information theory, Lecture Notes in Computer Science v, vol.3959, pp.327-338, 2006.

A. Shen, Algorithmic information theory and foundations of probability, P r o c . 3 r d W o r k s h, Lecture Notes in Computer Science v, vol.5797, pp.26-34, 2009.

A. Shen and A. Kolmogorov, F e s ts c h r if t f o r A, pp.75-116, 2015.

A. Shen, , 2017.

A. Shen and N. Vereshchagin, , pp.125-129, 2001.

A. Shen and N. K. Vereshchagin, Student Mathematical Library, vol.19, 2003.

M. Sipser, , 1996.

D. Slepian, J. K. Wolf, and . ;-i-e-e-e-t, Noiseless coding of correlated information sources, pp.471-480, 1973.

R. J. Solomonoff, A formal theory of inductive inference, pp.224-254, 1964.

R. Solovay, r s ) o n C h a itin 's w o r k , done for the most part during Sept, 1974.

R. M. Solovay, R. E. On-random, and . Sets, , pp.283-307, 1977.

K. Tadaki, A generalization of Chaitin's halting probability S7 and halting self-similar sets, pp.219-253, 2002.

H. Takahashi, On a definition of random sequences with respect to conditional probability, pp.1375-1382, 2008.

H. Takahashi, Algorithmic randomness and monotone complexity on product space, vol.209, pp.183-197, 2011.

V. Uspensky and A. Semenov, A lg o r ith m s, vol.269, p.pp, 1993.

V. A. Uspensky, A. L. Semenov, &. A. Shen, and . Kh, Can an individual sequence of zeros and ones be random? R u s s ia n M a th, pp.121-189, 1990.

V. A. Uspensky and A. Shen, Relations between varieties of Kolmogorov complexities, M a th e m a tic a l S y s te m s T h e o r y (now T h e o r y o f C o m p u tin g S y s t e m s ), pp.271-292, 1996.

N. K. Vereshchagin and . Kolmogorov, Preliminary version, vol.271, pp.1-086, 2001.

N. Vereshchagin, Kolmogorov complexity of enumerating finite sets, I n f o r m a tio n P r o c e s s in g L e tte r s , v, Preliminary version, vol.103, pp.34-39, 2004.

N. K. Vereshchagin, Kolmogorov complexity and games, pp.43-75, 2008.

N. Vereshchagin, Minimal sufficient statistic revisited, P r o c, Lecture Notes in Computer Science v, vol.5635, pp.478-487, 2009.

N. K. Vereshchagin, A. Shen, and . Ts,

N. Vereshchagin and A. Shen, Algorithmic statistics revisited, pp.235-252, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01233770

N. Vereshchagin and A. Shen, A lg o r, 2016.

N. K. Vereshchagin, P. M. Vitånyi, and . B-;-i-e-e-e-t, Kolmogorov's structure functions with an applica tion to the foundations of model selection, vol.50, pp.751-760, 2002.

N. K. Vereshchagin, P. M. Vitånyi, and . B-;-i-e-e-e-t, Rate distortion and denoising of individual data using Kolmogorov complexity, vol.56, pp.3438-3454, 2004.

N. Vereshchagin and M. Vyugin, Independent minimum length programs to translate be tween given strings, Preliminary version, vol.271, pp.0-035, 2000.

J. Ville, . Tu-tif, and . Gauthier-villars, Monographies des probabilités. Calcul des probabilités et ses applications, Publiée sous la direction de M. Émile Borel. Fascicule III, 1939.

V. G. Vovk, On a randomness criterion, vol.35, pp.656-660, 1987.

V. G. Vovk, The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences, vol.32, pp.413-425, 1987.

V. Vovk and V. V. V-'y-iig-in, On the empirical validity of Bayesian method, J ie ty, vol.55, pp.253-266, 1993.

V. V. V-'yugin, Nonstochastic objects, P io n, vol.21, pp.77-83, 1985.

V. V. V-'yiigin-;-s-i-a-m-t, On the defect of randomness of a finite object with respect to measures with given complexity bounds, vol.32, pp.508-512, 1987.

V. V. V-'yugin, Algorithmic complexity and stochastic properties of finite binary sequences, vol.42, pp.294-317, 1999.

V. V. V-'yugin, Algorithmic entropy (complexity) of finite objects and its applications to defining randomness and amount of information, vol.13, pp.357-389, 1994.

V. V. V-'yugin, Ergodic theorems for individual random sequences, pp.343-361, 1998.

V. V. V-'yugin, Non-stochastic infinite and finite sequences, T e , v, vol.207, pp.363-382, 1998.

A. Wald, Sur la notion de collectif dans le calcul des probabilités (On the notion of collective in probability theory), présentée par M. Émile Borel. C o m p te s r e n d u s , v, vol.202, pp.180-183

A. Wald, Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung, vol.8, pp.38-72, 1937.

D. D. Wall, N o r m a l N u m b e r s, 1949.

A. Wigderson, Randomness extractors-applications and constructionsc e, 2009.

R. W. Yeung, , 2002.

I. D. Zaslavsky and G. S. Tseitin, O singulyarnykh pokrytiyakh i svyazannykh s nimi svoistvah konstruktivnykh funktsii (Singular coverings and properties of constructive functions connected with them, vol.67, pp.458-502, 1962.

Z. Zhang, R. W. Yeung, and . ;-i-e-e-e-t, A non-Shannon-type conditional information inequality, vol.43, pp.1982-1986, 1997.

Z. Zhang, R. W. Yeung, and . ;-i-e-e-e-t, On characterization of entropy function via information inequalities, vol.44, pp.1440-1450, 1998.

M. Zimand and . Guest-column-;-s-i-g-a-c-t-n-e-w-s, Possibilities and Impossibilities in Kolmogorov complexity ex traction, 2010.

A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, R u s s ia n M a th, pp.83-124

T. A. Slaman, , vol.158, p.164

, A lexan d ru B u iu m , Foundations of Arithmetic Differential Geometry, 2017.

, D en n is G a itsg o ry an d N ick R o zen b ly u m , A Study in Derived Algebraic Geometry, 2017.

A. Shen and V. A. , U sp e n sk y , an d N . V eresh ch agin, 2017.

. R-ichard-e-van-sch-w-artz, , 2017.

. Id, M ariu sz U rb an sk i, Geometry and Dynamics in Gromov Hyperbolic Metric Spaces, 2017.

, B e n o it F resse, Homotopy of Operads and Grothendieck-Teichmiiller Groups, 2017.

F. , W. Eh-rin-g,-g-aven-j.-m-a-rtin, and P. Ru-ce, An Introduction to the Theory of Higher-Dimensional Quasiconformal Mappings, 2017.

B. R-o-b-ert, On Groups of PL-homeomorphisms of the Real Line, 2016.

J. Speck, Shock Formation in Small-Data Solutions to 3D Quasilinear Wave Equations, 2016.

H. , G. Ia-m-o-n-d-an-d-w-en--b-in, and Z. , Beurling Generalized Numbers, 2016.

C. , J a cq u es Sau loy, and M ich ael F. S in ger, Galois Theories of Linear Difference Equations: An Introduction, 2016.

P. So-n, T. H-o-m-a-s, and J. Ucker, The Dynamical Mordell, 2016.

. S-tev-e-y-.-o-u-d-ot, Persistence Theory: From Quiver Representations to Data Analysis, 2015.

S. P-e-te-r, A n d rås I. S tip sicz, an d Z oltån S zab o, Grid Homology for Knots and Links, 2015.

. V-lad-im-ir-i.-b-o-g-a-ch-ev, . Ic-o-la-i-v-.-k-rylov, E. Öck-n, S. Ta-n-isla-v-v-.-s-h-ap-osh-n-ik, and . Ov, , 2015.

. B-e-n-n-e-tt-c-how-,-s-u-n--c-h-in-c-hu, . Lick-en-stein-,-c-h-ristin-e-g-u-en, . Lu, and . Eng-luo, The Ricci Flow: Techniques and Applications: Part IV: Long-Time Solutions and Related Topics, 2015.

S. Tin-gof and . Lo-m-o-g-elak-i, D m itri N ik sh y ch , an d V ic to r O strik , Tensor Categories, 2015.

, A Foundation for PROPs, Algebras, and Modules, 2015.

D. Shiri-a-r-tste-;-v-ita-li, Asymptotic Geometric Analysis, Part I, 2015.

. 201-c-h-ristop-h-er-l.-d-o-u-g-la-s,-j-o-h-n-francis, A n d ré G . H en riq u es, and M ich ael A . H ill, E d itors, Topological Modular Forms, 2014.

S. V. Ladu, Nonlinear Elliptic Equations and Nonassociative Algebras, 2014.

S. D-m-itr-y and . Aliu, zh n y i-V erb o v etsk y i an d V ic to r V in n ik ov, Foundations of Free Noncommutative Function Theory, 2014.