I. Noga-alon, A. Newman, G. Shen, N. K. Tardos, and . Vereshchagin, Partitioning multi-dimensional sets in a small number of "uniform" parts, European Journal of Combinatorics, vol.28, issue.1, pp.134-144, 2007.

L. Antunes, S. Laplante, A. Pinto, and L. Salvador, Cryptographic Security of Individual Instances. Information theoretic security, LNCS, vol.4883, pp.195-210, 2009.

S. Cristian, P. H. Calude, B. Hertling, Y. Khoussainov, and . Wang, Recursively Enumerable Reals and Chaitin ? Numbers. Theoretical Computer Science, vol.255, pp.125-149, 2001.

T. H. Chan and R. W. Yeung, On a relation between information inequalities and group theory, IEEE Transaction on Information theory, vol.48, issue.7, pp.199-1995, 2002.

A. Chernov, A. A. Muchnik, A. E. Romashchenko, A. Shen, and N. K. Vereshchagin, Upper semi-lattice of binary strings with the relation "x is simple conditional to, Theoretical Computer Science, vol.271, issue.1-2, pp.69-95, 2002.

B. Durand, L. A. Levin, and A. Shen, Complex Tilings. Journal of Symbolic Logic, vol.73, issue.2, pp.593-613, 2007.

P. Gács and J. Korner, Common Information is Far Less Than Mutual Information. Problems of Control and Information Theory, vol.2, pp.119-162, 1973.

D. Hammer, A. E. Romashchenko, A. Shen, and N. Vereshchagin, Inequalities for Shannon Entropy and Kolmogorov Complexity, Journal for Computer and System Sciences, vol.60, pp.442-464, 2000.

D. Hammer and A. Shen, A Strange Application of Kolmogorov Complexity. Theory of Computing Systems, vol.31, pp.1-4, 1998.

O. Kristoffer-arnsfelt-hansen, P. Lachish, and . Bro-miltersen, Hilbert's Thirteenth Problem and Circuit Complexity, Lecture notes in computer science, vol.5878, pp.153-162, 2009.

A. N. Kolmogorov, Three approaches to the definition of the concept "quantity of information, Problemy Peredachi Informatsii (Russian), vol.1, issue.1, pp.3-11, 1965.

S. Kritchman and R. Raz, The Surprise Examination Paradox and the Second Incompleteness Theorem, Notices of the AMS, vol.75, issue.11, pp.1454-1458, 2010.

A. Ku?era and T. A. Slaman, Randomness and recursive enumerability, SIAM Journal on Computing, vol.31, issue.1, pp.199-211, 2001.

M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2008.

, Andrej Muchnik. Conditional complexity and codes. Theoretical Computer Science, vol.271, issue.1-2, pp.97-109, 2002.

H. Rogers, Theory of Recursive Functions and Effective Computability, 1967.

A. E. Romashchenko, A Criterion of Extractability of Mutual Information for a Triple of Strings, Problems of Information Transmission, vol.39, pp.148-157

A. E. Romashchenko, A. Shen, and N. K. Vereshchagin, Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science, vol.271, issue.1-2, pp.111-123, 2002.

A. Y. Rumyantsev and M. A. Ushakov, Forbidden substrings, Kolmogorov complexity and almost periodic sequences, STACS 2006, vol.3884, pp.396-407

A. Shen, Algorithmic Information theory and Kolmogorov complexity

A. Shen, Available as hal-00541921 at archives-ouvertes, Decomposition complexity. Journées Automates Cellulaires 2010 (Turku), pp.203-213

Y. Ti, C. Chang, Y. Lyuu, and A. Shen, Sets of k-independent strings, International Journal of Foundations of Computer Science, vol.21, issue.3, pp.321-327, 2010.