, \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
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 ,
, A lg o r ith m s, vol.269, p.pp, 1993.
Can an individual sequence of zeros and ones be ran dom?" R u s s ia n M a th, pp.121-189, 1990. ,
Relations between varieties of Kolmogorov complexities, vol.29, pp.271-292, 1996. ,
Mathematical metaphysics of randomness, vol.207, pp.263-317, 1998. ,
On relations between different algorithmic definitions of randomness, vol.38, pp.316-319, 1989. ,
Network Information Flow, vol.46, pp.1204-1216, 2000. ,
On common information and related characteristics of correlated in formation sources, Preprint, Presented at the 7th Prague Conference on Information Theory, 1974. ,
Partitioning multi-dimensional sets in a small number of, vol.28, pp.5-095, 2005. ,
, , pp.195-204, 2016.
Plain and prefix complexity characterizations of 2-randomness: simple proofs, vol.54, pp.615-629, 2013. ,
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
, , 2016.
Turing unpublished algorithm for normal numbers, vol.377, pp.126-138, 2007. ,
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. ,
G a m e -st i c i t, 2008. ,
Generic algorithms for halting problem and optimal machines revisited, v, vol.12, pp.1-29, 2016. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01233778
6 th S y m p, vol.2, p.2009, 2009. ,
Algorithmic tests and randomness with respect to a class of measures, P r o c, vol.274, pp.41-102, 2011. ,
Randomness and semi-measures ,
,
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. ,
The dynamics of cellular automata in shift-invariant topologies, Lecture Notes in Computer Science, v, vol.1, pp.84-95, 2007. ,
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. ,
, Algorithmic information theory and martingales
Random semicomputable reals revisited, Lecture Notes in Computer Science, pp.31-45, 2012. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00845796
, Lecture Notes in Computer Science, vol.9300, pp.1-23, 2015.
L e h a s a r d, 1920. ,
English translation: Borei E, 1961. ,
, , pp.887-905, 2002.
Increasing Kolmogorov complexity, P r o c . 2 2 n d S y m p, STACS 2005), vol.3404, pp.4-081, 2004. ,
, , pp.450-453, 1994.
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. ,
On partial randomness, pp.20-30, 2006. ,
On the length of programs for computing binary sequences, vol.13, pp.547-569, 1966. ,
On the length of programs for computing binary sequences: statistical con siderations, vol.16, pp.145-159, 1969. ,
Computational complexity and GödePs incompleteness theorem, pp.11-12, 1971. ,
Information-theoretic limitations of formal systems, vol.21, pp.403-424, 1974. ,
A theory of program size formally identical to information theory, vol.22, pp.329-340, 1975. ,
Information-theoretic characterizations of recursive infinite strings, vol.1, pp.45-48, 1976. ,
Incompleteness theorems for random reals, A d v tic s , v, vol.8, pp.119-146, 1987. ,
, A lg o r ith m ic i n f o r m a tio n th e o r y, 1987.
The construction of decimals normal in the scale of ten, pp.254-260, 1933. ,
On a relation between information inequalities and group theory, vol.48, 1992. ,
Complexity of sets obtained as values of propositional formulas, pp.131-139, 2004. ,
Upper semi lattice of binary strings with the relation "x is simple conditional to, pp.114-122, 1999. ,
Algorithmic complexity bounds on future prediction errors, p.205, 2007. ,
On-line Probability, Complexity and Ran domness, P r o c, pp.138-153, 2008. ,
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. ,
Some intersection theorems for ordered sets and graphs, vol.43, pp.23-37, 1986. ,
On the concept of a random sequence, vol.46, pp.130-135, 1940. ,
, A lg o r ith m s, 2009.
, 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.
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. ,
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. ,
, , pp.855-978, 2010.
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. ,
, , vol.73, pp.593-613, 2007.
Descriptive complexity of computable sequences, Lecture Notes in Computer Science v. 1563, vol.171, pp.1-087, 1999. ,
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. ,
Kolmogorov complexity with error, Lecture Notes in Computer Science v, vol.3884, pp.4-080, 2004. ,
On the symmetry of algorithmic information, vol.15, pp.1477-1480, 1974. ,
Exact expressions for some randomness test, vol.26, pp.385-394, 1980. ,
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. ,
Every sequence is reducible to a random one, pp.186-192, 1986. ,
Common information is far less than mutual information, pp.149-162, 1973. ,
Algorithmic statistics, I E E r, vol.47, pp.2443-2463, 2001. ,
, , 2007.
, , pp.383-386, 1998.
, , vol.292, 1950.
Inequalities for Shannon entropies and Kolmogorov complexities, vol.60, pp.13-23, 1997. ,
A strange application of Kolmogorov complexity, S y s te m s, pp.1-4, 1998. ,
Probability inequalities for sums of bounded random variables, vol.58, pp.13-30, 1963. ,
Time-bounded Kolmogorov complexity and Solovay func tions, Lecture Notes in Computer Science v, vol.5734, pp.392-402, 2009. ,
, A lg o r ith m ic P r o b a b ility, vol.278, 2005.
Extractors and pseudo-random generators with optimal seed length, pp.1-10, 2000. ,
On equivalence of infinite product measures, Second Series, v, vol.49, issue.1, pp.214-224, 1948. ,
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.
Monotone complexity of a pair, P r o c . s ia (CSR 2010), Lecture Notes in Computer Science v, vol.6072, pp.266-275 ,
The probability distribution as a computational resource for randomness testing, 2010. ,
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. ,
On the interpretation of intuitionistic number theory, pp.109-124, 1945. ,
, 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.
On tables of random numbers, vol.25, pp.387-395, 1963. ,
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. ,
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. ,
Combinatorial foundations of information theory and the calculus of probabilities, pp.29-40, 1983. ,
, , vol.403, 1970.
, Talk at the Information Theory Symposium in, 1974.
The definition of (a, /3)-stochasticity was given in this talk, and the question about the fraction of non-stochastic objects was asked, 1981. ,
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.
, 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.
, , pp.199-211, 2001.
, , 1949.
, 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
, , 1987.
Computability by probabilis tic machines, pp.183-212, 1956. ,
dissertation directed by A. N. Kolmogorov; turned down as required by the Soviet authorities despite unanimously positive reviews), pp.224-235, 1971. ,
On the notion of a random sequence, pp.1413-1416, 1973. ,
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. ,
Various measures of complexity for finite objects (axiomatic description, vol.17, pp.522-526, 1976. ,
On the principle of conservation of information in intuitionistic mathematics, vol.17, pp.601-605, 1976. ,
Uniform tests of randomness, vol.17, pp.337-340, 1976. ,
On a concrete method of assigning complexity measures, vol.18, pp.727-731, 1977. ,
A concept of independence with application in various fields of mathematics, vol.21, p.pp, 1980. ,
Randomness conservation inequalities: information and independence in math ematical theories, pp.15-37, 1984. ,
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. ,
Preliminary version, P r o c . 4 3 th I E E E S y m p, pp.761-768, 2002. ,
, , vol.2, 1993.
Linear network coding, pp.371-381, 2003. ,
URL : https://hal.archives-ouvertes.fr/hal-01327498
An inequality related to the isoperimetric inequality, vol.55, pp.961-962, 1949. ,
A new interpretation of von Mises' concept of a random sequence, pp.279-294, 1966. ,
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. ,
A Variant of the Kolmogorov concept of complexity, pp.510-526, 1969. ,
On minimal-program complexity measures, P r o c . 1 s t A C M S y m p, pp.61-65, 1969. ,
Preliminary version, P r o c . 1 5 th I E E E C, Dimension in complexity classes, vol.32, pp.158-169, 2000. ,
Preliminary version, Gales and the constructive dimension of individual sequences, Lecture Notes in Computer Science v, vol.187, issue.1, pp.902-913, 2000. ,
, , vol.58, pp.5279-5286, 2012.
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.
The definition of random sequences, I ta tio n ), pp.602-619, 1966. ,
Vier Vorträge von Per Martin-Löf (Stockholm) gehalten am Mathematischen, p.61, 1966. ,
Complexity oscillations in infinite binary sequences, pp.225-230, 1971. ,
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. ,
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.
The complexity of stochastic sequences, P r o c . le x ity, pp.230-235, 2003. ,
Every 2-random real is Kolmogorov random, pp.907-913, 2004. ,
Contrasting plain and prefix-free Kolmogorov complexity, www.math. w ise ,
On initial segment complexity and degrees of randomness, vol.360, pp.3193-3210, 2008. ,
The ? -Degrees, low for ? degrees, and weakly low for ? sets, vol.50, pp.381-391, 2009. ,
Two notes on subshifts, pp.1617-1622, 2012. ,
, Z e its c h r if t, Bd, vol.5, pp.57-106, 1919.
, , p.189, 1928.
S ta t i s t i c s , v, On the foundations of probability and statistics, vol.12, pp.340-355, 1941. ,
Discussion of papers on probability theory, vol.12, pp.356-359, 1941. ,
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. ,
A constructive proof of the general Lovasz Local Lemma, vol.57, 2010. ,
On the basic structures of the descriptive theory of algorithms, vol.32, pp.671-674, 1985. ,
Lower limits on frequencies in computable sequences and relativized a priori probability, pp.513-514, 1987. ,
On common information, vol.207, pp.319-328, 1998. ,
Preliminary version, Muchnik A., Semenov A., Multi-conditional descriptions and codes in Kolmogorov complexity, vol.271, pp.0-015, 2000. ,
, , 2010.
Kolmogorov entropy in the context of computability theory, pp.15-35, 2002. ,
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. ,
Mathematical metaphysics of randomness, vol.207, pp.263-317, 1998. ,
Non-reducible descriptions for conditional Kolmogorov complexity, Non-reducible de scriptions for conditional Kolmogorov complexity, vol.384, pp.4-054, 2004. ,
, Shannon entropy vs. Kolmogorov complexity
, R u s s ia, vol.3967, pp.281-291, 2006.
Preliminary versions, Much nik An. A., Vereshchagin N .K ., Logical operations and Kolmogorov complexity, vol.274, pp.90-104, 2011. ,
, , pp.1-089, 2001.
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. ,
, 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.
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.
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. ,
, , vol.420, 2009.
Randomness, relativization and Turing degrees, vol.70, pp.515-535, 2005. ,
, , 2016.
On non-computable functions, vol.3, pp.877-884, 1962. ,
, Common information revisited, 2012.
,
, , p.80, 2011.
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. ,
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. ,
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. ,
Infinite computable version of Lovasz Local Lemma, 2010. ,
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. ,
On normal numbers, pp.661-672, 1960. ,
, Eine Bemerkung zum Begriff der zufälligen Folge, Z d V e rw . G e b ie te, vol.14, pp.27-35, 1969.
Uber die Definition effektiver Zufallstests, Teil I, Z d V e rw . G e b ie te, vol.15, pp.297-312, 1970. ,
Uber die Definition effektiver Zufallstests, Teil II, Z d V e rw . G e b ie te, vol.15, pp.313-328, 1970. ,
, 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.
, Lecture Notes in Mathematics, 1971.
A unified approach to the definition of random sequences, pp.246-258, 1971. ,
, , pp.56-58, 1971.
, Process complexity and effective random tests, pp.168-176, 1973.
, 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.
Test martingales, Bayes factors, and p-values, vol.26, pp.84-101, 2011. ,
, , 2001.
, , pp.104-105, 1982.
The concept of (a,/3)-stochasticity in the Kolmogorov sense, and its properties, vol.28, pp.295-299, 1983. ,
, On logical foundations of applications of probability theory
Algorithmic variants of the notion of entropy, vol.29, pp.569-573, 1984. ,
On relations between different algorithmic definitions of randomness, vol.38, pp.316-319, 1989. ,
, Discussion on Kolmogorov Complexity and Statistical Analysis, vol.42, pp.340-342, 1999.
Multisource algorithmic information theory, Lecture Notes in Computer Science v, vol.3959, pp.327-338, 2006. ,
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. ,
F e s ts c h r if t f o r A, pp.75-116, 2015. ,
, , 2017.
, , pp.125-129, 2001.
, Student Mathematical Library, vol.19, 2003.
, , 1996.
Noiseless coding of correlated information sources, pp.471-480, 1973. ,
A formal theory of inductive inference, pp.224-254, 1964. ,
r s ) o n C h a itin 's w o r k , done for the most part during Sept, 1974. ,
, , pp.283-307, 1977.
A generalization of Chaitin's halting probability S7 and halting self-similar sets, pp.219-253, 2002. ,
On a definition of random sequences with respect to conditional probability, pp.1375-1382, 2008. ,
Algorithmic randomness and monotone complexity on product space, vol.209, pp.183-197, 2011. ,
, A lg o r ith m s, vol.269, p.pp, 1993.
Can an individual sequence of zeros and ones be random? R u s s ia n M a th, pp.121-189, 1990. ,
, 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.
, Preliminary version, vol.271, pp.1-086, 2001.
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. ,
Kolmogorov complexity and games, pp.43-75, 2008. ,
Minimal sufficient statistic revisited, P r o c, Lecture Notes in Computer Science v, vol.5635, pp.478-487, 2009. ,
,
, Algorithmic statistics revisited, pp.235-252, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01233770
, A lg o r, 2016.
Kolmogorov's structure functions with an applica tion to the foundations of model selection, vol.50, pp.751-760, 2002. ,
Rate distortion and denoising of individual data using Kolmogorov complexity, vol.56, pp.3438-3454, 2004. ,
Independent minimum length programs to translate be tween given strings, Preliminary version, vol.271, pp.0-035, 2000. ,
Monographies des probabilités. Calcul des probabilités et ses applications, Publiée sous la direction de M. Émile Borel. Fascicule III, 1939. ,
On a randomness criterion, vol.35, pp.656-660, 1987. ,
The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences, vol.32, pp.413-425, 1987. ,
On the empirical validity of Bayesian method, J ie ty, vol.55, pp.253-266, 1993. ,
Nonstochastic objects, P io n, vol.21, pp.77-83, 1985. ,
On the defect of randomness of a finite object with respect to measures with given complexity bounds, vol.32, pp.508-512, 1987. ,
Algorithmic complexity and stochastic properties of finite binary sequences, vol.42, pp.294-317, 1999. ,
Algorithmic entropy (complexity) of finite objects and its applications to defining randomness and amount of information, vol.13, pp.357-389, 1994. ,
Ergodic theorems for individual random sequences, pp.343-361, 1998. ,
Non-stochastic infinite and finite sequences, T e , v, vol.207, pp.363-382, 1998. ,
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 ,
, Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung, vol.8, pp.38-72, 1937.
, N o r m a l N u m b e r s, 1949.
, Randomness extractors-applications and constructionsc e, 2009.
, , 2002.
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. ,
A non-Shannon-type conditional information inequality, vol.43, pp.1982-1986, 1997. ,
On characterization of entropy function via information inequalities, vol.44, pp.1440-1450, 1998. ,
Possibilities and Impossibilities in Kolmogorov complexity ex traction, 2010. ,
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 ,
, , 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.
U sp e n sk y , an d N . V eresh ch agin, 2017. ,
, , 2017.
, 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.
An Introduction to the Theory of Higher-Dimensional Quasiconformal Mappings, 2017. ,
On Groups of PL-homeomorphisms of the Real Line, 2016. ,
Shock Formation in Small-Data Solutions to 3D Quasilinear Wave Equations, 2016. ,
, Beurling Generalized Numbers, 2016.
, J a cq u es Sau loy, and M ich ael F. S in ger, Galois Theories of Linear Difference Equations: An Introduction, 2016.
, The Dynamical Mordell, 2016.
, Persistence Theory: From Quiver Representations to Data Analysis, 2015.
A n d rås I. S tip sicz, an d Z oltån S zab o, Grid Homology for Knots and Links, 2015. ,
, , 2015.
, The Ricci Flow: Techniques and Applications: Part IV: Long-Time Solutions and Related Topics, 2015.
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.
, Asymptotic Geometric Analysis, Part I, 2015.
, A n d ré G . H en riq u es, and M ich ael A . H ill, E d itors, Topological Modular Forms, 2014.
, Nonlinear Elliptic Equations and Nonassociative Algebras, 2014.
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. ,