. .. Flexible-zoom-factors, 113 2.5.2 Embedding an infinite sequence in tiling and enforcing the non-computability of every configuration, p.117

S. .. Quasiperiodic-self-simulating, 119 2.6.1 Preliminary remarks: Supplementary constraints that can be imposed on a self-simulating tiling

M. .. Aperiodicity,

N. .. Quasiperiodicity, , p.126

, On the subdynamics of co-dimension 1 for self-simulating SFTs, p.128

K. High and . .. Sfts, 135 2.11.2 A technical tool for robust tilings (1): hierarchical islands of errors

. , Robust self-simulating tilings with variable zoom factors

, Error-correcting procedure

, 6, and let ? > 0 be a small enough real. Lemma 2.21 implies that a B ?-random set with probability 1 is bi-sparse. We fix a bi-sparse set E ? Z 2 (for the values of ? i and ? i chosen above), and a ?-tiling T of Z 2 \ E

, These clusters touch only O(1) macro-tiles of level (k?1). The distance between S 0 and S 1 is at most ? k , and we assume that the ? k-neighborhood of S has already been cleaned of other errors. In what follows we perform a correction procedure around S that involves only points in the extended ? k-neighborhood of S, where ? k = 2? k. Let M be a k-level macro-tile intersecting the extended ? k-neighborhood of S. We want to find a repaired version of M. Basically, we need to reconstruct the "correct" versions of all (k ? 1)-level macro-tiles inside M damaged by S. We start by reconstructing the conscious information in all (k ? 1)-level macro-tiles in M. This is enough to get all bits of the embedded sequence x from the "zone of responsibility, Since E is bi-sparse, it can be represented as a union of isolated bi-islands of different ranks. We now correct these bi-islands one by one, starting from bi-islands of low ranks

, the binary representation of the number (k ? 1) and of the coordinates of M in the father macro-tile M

, the bits used to simulate a Turing machine on the computation zone of M and the bits used to implement the communication wires of M

, the bit (from the embedded sequence x) delegated to M

, the bit (from x) delegated to M

, the bits used to calculate and communicate the checksums for the corresponding row of (k ? 1)-level macro-tiles in M

, Thus, the bits delegated to the corresponding (k ? 1)-level macro-tiles inside M u and M d are equal to each other except for only (k ? 1)-level macro-tiles in the "gray zone" in Fig. 2.26, which contains the vertical stripe of columns that go through the (k ? 1)-level macro-tiles involved in the correction of S. The width of this stripe is O(1) macro-tiles of level (k ? 1). Hence, for i = 0,. .. , (N k?1 ? 1), if we compare the i th rows of (k ? 1)-level macro-tiles in M u and in M d , we see that the sequences of delegated bits are equal to each other except possibly for only O(1) bits (delegated to (k ? 1)-level macro-tiles in the gray zone), inside M u and M d is consistent with these bits. Hence, these bits x i are correctly delegated to the corresponding (k ? 1)-level macro-tiles inside M u and M d. However, it is not evident that the sequences of L k bits embedded in M u and in M d are equal to each other. We start with an observation that bit sequences for M u and M d coincide with each other at most positions. Indeed, they match for all columns (from the range 0

D. Chumbalov and A. Romashchenko, On the Combinatorial Version of the SlepianWolf Problem, IEEE Transactions on Information Theory, vol.64, issue.9, pp.6054-6069, 2018.
URL : https://hal.archives-ouvertes.fr/lirmm-01233020

T. Kaced, A. Romashchenko, and N. Vereshchagin, Conditional Information Inequalities and Combinatorial Application, IEEE Transactions on Information Theory, vol.64, pp.3610-3615, 2018.

A. Romashchenko and A. Shen, Topological Arguments for Kolmogorov Complexity, Theory of Computing Systems, vol.56, pp.513-526, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01165095

L. Bienvenu, A. Romashchenko, A. Shen, A. Taveneaux, and S. Vermeeren, The axiomatic power of Kolmogorov complexity, Annals of Pure and Applied Logic, vol.165, pp.1380-1402, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01165098

A. Romashchenko, Pseudo-random graphs and bit probe schemes with one-sided error, Theory of Computing Systems, vol.55, pp.313-329, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-00736119

T. Kaced and A. Romashchenko, Conditional Information Inequalities for Entropic and Almost Entropic Points, IEEE Transactions on Information Theory, vol.59, pp.7149-7167, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00848455

B. Durand, A. Romashchenko, and A. Shen, Fixed-point tile sets and their applications, Journal of Computer and System Sciences, vol.78, issue.3, pp.731-764, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00736079

D. Musatov, A. Romashchenko, and A. Shen, Variations on Muchnik's Conditional Complexity Theorem. Theory of Computing Systems, vol.49, pp.227-245, 2011.

. An, A. Muchnik, and . Romashchenko, Stability of properties of Kolmogorov complexity under relativization, Problems of Information Transmission, vol.46, issue.1, pp.38-61, 2010.

B. Durand, A. Romashchenko, and A. Shen, Fixed point theorem and aperiodic tilings. The Logic in Computer Science Column by Yuri Gurevich, Bulletin of the EATCS, vol.97, pp.126-136, 2009.

T. Lee and A. Romashchenko, Resource Bounded Symmetry of Information Revisited, Theoretical Computer Science, vol.345, issue.2-3, pp.386-405, 2005.

A. Romashchenko, A Criterion of Extractability of Mutual Information for a Triple of strings, Problems of Information Transmission, vol.39, issue.1, pp.148-157, 2003.

K. Makarychev, Y. Makarychev, A. Romashchenko, and N. Vereshchagin, A New Class of non Shannon type inequalities for Entropies, Communications in Information and Systems, pp.147-166, 2002.

A. Romashchenko, A. Shen, and N. Vereshchagin, (version préliminaire dans Proc. of 15th Annual IEEE Conference on Computational Complexity, vol.271, pp.111-123, 2002.

A. Chernov, A. A. Muchnik, A. Shen, A. Romashchenko, and N. Vereshchagin, Upper semi-lattice of binary strings with the relation x is simple conditional to, (version préliminaire dans Proc. of 14th Annual IEEE Conference on Computational Complexity, vol.271, pp.69-95, 2002.

D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, Inequalities for Shannon Entropy and Kolmogorov Complexity, (version préliminaire dans Proc. of 13th Annual IEEE Conference on Computational Complexity, vol.60, pp.442-464, 2000.

A. Romashchenko, Pairs of Words with Nonmaterializable Mutual Information, Problems of Information Transmission, vol.36, issue.1, pp.1-18, 2000.

A. Romashchenko, Sequences of binary strings with relation of conditional simplicity, Moscow University Mathematics Bulletin, vol.55, issue.5, pp.20-22, 2000.

, Actes de conférences les plus significatives avec comité de lecture

A. Romashchenko and M. Zimand, An operational characterization of mutual information in algorithmic information theory, Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018. Track A. 95:1-95:14. (version étendue dans Electronic Colloquium on Computational Complexity
URL : https://hal.archives-ouvertes.fr/lirmm-01618559

B. Durand and A. Romashchenko, On the expressive power of quasiperiodic SFT
URL : https://hal.archives-ouvertes.fr/lirmm-01623207

, Proc. 43 International Symposium on Mathematical Foundations of Computer Science (MFCS, vol.5, pp.1-14, 2017.

D. Itsykson, A. Knop, A. Romashchenko, and D. Sokolov, On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables, Proc. 34th Symposium on Theoretical Aspects of Computer Science (STACS, vol.43, pp.1-14, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01487646

B. Durand and A. Romashchenko, Quasiperiodicity and Non-computability in
URL : https://hal.archives-ouvertes.fr/lirmm-01165314

. Tilings, Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS) (2015), Part 1, pp.218-230

D. Chumbalov and A. Romashchenko, Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem, Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pp.235-247, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01233012

A. Romashchenko, Pseudo-random graphs and bit probe schemes with one-sided error, Proc. 6th International Computer Science Symposium in Russia (CSR)
URL : https://hal.archives-ouvertes.fr/lirmm-00736119

. Saint-petersburg, Lecture Notes in Computer Science, vol.6651, pp.50-63, 2011.

B. Durand, A. Romashchenko, and A. Shen, High complexity tilings with sparse errors, Proc. of 36th International Colloquium on Automata, Languages, and Programming (ICALP) 1, pp.403-414, 2009.

D. Musatov, A. Romashchenko, and A. Shen, Variations on Muchnik's Conditional Complexity Theorem, Proc. 4th International Computer Science Symposium in Russia (CSR), pp.250-262, 2009.

B. Durand, A. Romashchenko, and A. Shen, Fixed Point and Aperiodic Tilings, Proc. 12th International Conference on Developments in Language Theory (DLT)
URL : https://hal.archives-ouvertes.fr/hal-00256364

J. Kyoto, , pp.537-548, 2008.

. A. An, A. E. Muchnik, and . Romashchenko, A Random Oracle Does Not Help Extract the Mutual Information, Proc. 33rd International Symposium Mathematical Foundations of Computer Science (MFCS), pp.527-538, 2008.

A. Romashchenko, Reliable Computations Based on Locally Decodable Codes
URL : https://hal.archives-ouvertes.fr/hal-00293698

, Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp.537-548, 2006.

T. Lee and A. Romashchenko, On Polynomially Time Bounded Symmetry of Information, Proc. 29th Symposium on the Mathematical Foundations of Computer Science (MFCS), pp.463-475, 2004.

A. Romashchenko, Extracting the Mutual Information for a Triple of Binary Strings, Proc. 18th Annual IEEE Conference on Computational Complexity (CCC), pp.221-229, 2003.

A. Romashchenko, A. Shen, and N. Vereshchagin, Combinatorial Interpretation of Kolmogorov Complexity, Proc. 15th Annual IEEE Conference on Computational Complexity (CCC), pp.131-138, 2000.

. A. An, A. Muchnik, A. Shen, N. Romashchenko, and . Vereshchagin, Upper semilattice of binary strings with the relation x is simple conditional to, Proc. 14th

, Annual IEEE Conference on Computational Complexity (CCC), pp.114-122, 1999.

D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, Inequalities for Shannon entropies and Kolmogorov complexities, Proc. Twelfth Annual IEEE Conference on Computational Complexity (CCC), pp.13-23, 1997.

, Actes d'autres colloques et workshops avec comité de lecture

T. Kaced and A. Romashchenko, On the Non-robustness of Essentially Conditional Information Inequalities, IEEE Information Theory Workshop, pp.262-266, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00736192

A. Shen and A. Romashchenko, Topological arguments for Kolmogorov complexity, Proc. 18th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) (2012), pp.127-132
URL : https://hal.archives-ouvertes.fr/lirmm-00736127

B. Durand, A. Romashchenko, and A. Shen, Effective Closed Subshifts in 1D Can Be Implemented in 2D. Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, Lecture Notes in Computer Science, vol.300, pp.208-226, 2010.

T. Kaced and A. Romashchenko, On essentially conditional information inequalities, Proc. IEEE Int. Sympos. on Information Theory (ISIT), pp.1935-1939, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00736159

A. Shen, L. Bienvenu, and A. Romashchenko, Sparse sets, Proceedings of the First Symposium on Cellular Automata 'Journées Automates Cellulaires' (JAC), pp.18-28, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00274010

B. Durand and A. Romashchenko, On stability of computations by cellular automata, Proc. European Conf. Compl. Syst, 2005.

. Livres,

A. Shen, A. Romashchenko, and A. Rumyantsev, Notes on Coding Theory, Russian) MCCME Publishers, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-01486509

A. Romashchenko and M. Zimand, An operational characterization of mutual information in algorithmic information theory, Electronic Colloquium on Computational Complexity (ECCC), vol.36, pp.18-043, 2018.
URL : https://hal.archives-ouvertes.fr/lirmm-01618559

B. Durand and A. Romashchenko, The expressiveness of quasiperiodic and minimal shifts of finite type, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01702549

R. V. Hartley, Transmission of information, Bell Labs Technical Journal, vol.7, issue.3, pp.535-563, 1928.

C. E. Shannon, Communication theory of secrecy systems, Bell Sys. Tech. Jour, vol.28, pp.623-656, 1948.

A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform. Transmission, vol.1, issue.1, pp.1-7, 1965.

R. Berger, The undecidability of the domino problem, vol.66, 1966.

F. C. Hennie and R. E. Stearns, Two-tape simulation of multitape turing machines, Journal of the ACM, vol.13, issue.4, pp.533-546, 1966.

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

B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol.13, issue.7, pp.422-426, 1970.

A. Zvonkin and L. Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys, vol.25, issue.6, pp.83-124, 1970.

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones mathematicae, vol.12, issue.3, pp.177-209, 1971.

L. Bassalygo and M. Pinsker, The complexity of an optimal non-blocking commutation scheme without reorganization, Problems of Information Transmission, vol.9, issue.1, pp.84-87, 1973.

P. Gács and J. Körner, Common information is far less than mutual information, Probl. Control Inf. Theory, vol.2, issue.2, pp.149-162, 1973.

M. S. Pinsker, On the complexity of a concentrator, 7th International Telegraffic Conference, Citeseer, vol.4, pp.1-318, 1973.

D. Slepian and J. Wolf, Noiseless coding of correlated information sources, IEEE Transactions on Information Theory, vol.19, issue.4, pp.471-480, 1973.

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

W. Hanf, Nonrecursive tilings of the plane. I, The Journal of Symbolic Logic, vol.39, issue.2, pp.283-285, 1974.

D. Myers, Nonrecursive tilings of the plane. II, The Journal of Symbolic Logic, vol.39, issue.2, pp.286-294, 1974.

R. Ahlswede and J. Korner, Source coding with side information and a converse for degraded broadcast channels, IEEE Transactions on Information Theory, vol.21, issue.6, pp.629-637, 1975.

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

A. N. Kolmogorov, Talk at the seminar at moscow state university mathematics department (logic division), 1981.

P. Van-emde and . Boas, Dominoes are forever, 1983.

A. Kh and . Shen, The concept of (?, ?)-stochasticity in the Kolmogorov sense, and its properties, Soviet Math. Dokl, vol.28, pp.295-299, 1983.

M. L. Fredman, J. Komlós, and E. Szemerédi, Storing a sparse table with 0 (1) worst case access time, Journal of the ACM, vol.31, issue.3, pp.538-544, 1984.

F. R. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some intersection theorems for ordered sets and graphs, Journal of Combinatorial Theory, Series A, vol.43, issue.1, pp.23-37, 1986.

P. Gács, Reliable computation with cellular automata, Journal of Computer and System Sciences, vol.32, issue.1, pp.15-78, 1986.

B. Grünbaum and G. C. Shephard, Tilings and patterns, 1987.

A. Fiat, M. Naor, J. Schmidt, and A. Siegel, Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, pp.367-376, 1988.

P. Gács, Lecture notes on descriptional complexity and randomness, 1988.

L. S. Levitov, Local rules for quasicrystals, Communications in mathematical physics, vol.119, issue.4, pp.627-666, 1988.

N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, vol.12, issue.4, pp.449-461, 1992.

R. Ahlswede and I. Csiszár, Common randomness in information theory and cryptography-I: secret sharing, IEEE Trans. Information Theory, vol.39, issue.4, pp.1121-1132, 1993.

U. M. Maurer, Secret key agreement by public discussion from common information, IEEE Trans. Information Theory, vol.39, issue.3, pp.733-742, 1993.

N. Nisan and A. Wigderson, Hardness vs randomness, Journal of computer and System Sciences, vol.49, issue.2, pp.149-167, 1994.

B. Bollobás and A. Thomason, Projections of bodies and hereditary properties of hypergraphs, Bulletin of the London Mathematical Society, vol.27, issue.5, pp.417-424, 1995.

N. Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM, vol.42, issue.5, pp.1091-1106, 1995.

F. Matú?, Conditional independences among four random variables ii, Combinatorics, Probability and Computing, vol.4, issue.4, pp.407-417, 1995.

K. Culik and . Ii, An aperiodic set of 13 wang tiles, Discrete Mathematics, vol.160, issue.1-3, pp.245-251, 1996.

J. Kari, A small aperiodic set of wang tiles, Discrete Mathematics, vol.160, issue.1-3, pp.259-264, 1996.

J. , V. Neumann, and A. W. Burks, Theory of self-reproducing automata, 1996.

C. Allauzen, B. Durand, ;. E. Borger, E. Gradel, and Y. Gurevich, The classical decision problem, 1997.

E. Kushilevitz and N. Nisan, Communication complexity. Cambridge, 1997.

Z. Zhang and R. W. Yeung, A non-Shannon-type conditional inequality of information quantities, IEEE Transactions on Information Theory, vol.43, issue.6, pp.1982-1986, 1997.

C. H. Bennett, P. Gács, M. Li, P. M. Vitányi, and W. H. Zurek, Information distance, IEEE Transactions on information theory, vol.44, issue.4, pp.1407-1423, 1998.

. A. An and . Muchnik, On common information, Theor. Comput. Sci, vol.207, pp.319-328, 1998.

Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities, IEEE Transactions on Information Theory, vol.44, issue.4, pp.1440-1452, 1998.

A. Brodnik and J. I. Munro, Membership in constant time and almostminimum space, SIAM Journal on Computing, vol.28, issue.5, pp.1627-1640, 1999.

B. Durand, Tilings and quasiperiodicity, Theoretical Computer Science, vol.221, issue.1-2, pp.61-75, 1999.
URL : https://hal.archives-ouvertes.fr/lirmm-01165314

L. Trevisan, Constructions of near-optimal extractors using pseudo-random generators, Proceedings of the 30th ACM Symposium on Theory of Computing, pp.141-148, 1999.

J. Radhakrishnan and A. Ta-shma, Bounds for dispersers, extractors, and depth-two superconcentrators, SIAM Journal on Discrete Mathematics, vol.13, issue.1, pp.2-24, 2000.

H. Buhrman, L. Fortnow, and S. Laplante, Resource-bounded Kolmogorov complexity revisited, SIAM Journal on Computing, vol.31, issue.3, pp.887-905, 2001.

L. F. Gray, A reader's guide to gacs's "positive rates" paper, Journal of Statistical Physics, vol.103, issue.1-2, pp.1-44, 2001.

R. Pagh, Low redundancy in static dictionaries with constant query time, SIAM Journal on Computing, vol.31, issue.2, pp.353-363, 2001.

, On the cell probe complexity of membership and perfect hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.425-432, 2001.

A. Ta-shma, C. Umans, and D. Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.143-152, 2001.

H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh, Are bitvectors optimal?, SIAM Journal on Computing, vol.31, issue.6, pp.1723-1744, 2002.

. A. An and . Muchnik, Conditional complexity and codes, Theor. Comput. Sci, vol.271, issue.1-2, pp.97-109, 2002.

A. Ta-shma, Storing information with extractors, Information Processing Letters, vol.83, issue.5, pp.267-274, 2002.

L. Devroye and P. Morin, Cuckoo hashing: further analysis, Information Processing Letters, vol.86, issue.4, pp.215-219, 2003.

Y. Horibe, A note on Kolmogorov complexity and entropy, vol.16, pp.1129-1130, 2003.

I. Csiszár and P. Narayan, Secrecy capacities for multiple terminals, IEEE Trans. Information Theory, vol.50, issue.12, pp.3047-3061, 2004.

R. Pagh and F. F. Rodler, Cuckoo hashing, Journal of Algorithms, vol.51, issue.2, pp.122-144, 2004.

H. Buhrman, T. Lee, and D. Van-melkebeek, Language compression and pseudorandom generators, Computational Complexity, vol.14, issue.3, pp.228-255, 2005.

B. Durand, L. Levin, and A. Shen, Local rules and global order, or aperiodic tilings, The Mathematical Intelligencer, vol.27, pp.64-68, 2005.

L. A. Levin, Aperiodic tilings: breaking translational symmetry, The Computer Journal, vol.48, issue.6, pp.642-645, 2005.

R. Ahlswede and J. Körner, On common information and related characteristics of correlated information sources, General Theory of Information Transfer and Combinatorics, pp.664-677, 2006.

T. M. Cover and J. A. Thomas, Elements of information theory, 2006.

S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society, vol.43, issue.4, pp.439-561, 2006.

O. Reingold, R. Shaltiel, and A. Wigderson, Extracting randomness via repeated condensing, SIAM Journal on Computing, vol.35, issue.5, pp.1185-1209, 2006.

A. Yu, M. A. Rumyantsev, and . Ushakov, Forbidden substrings, Kolmogorov complexity and almost periodic sequences, Annual Symposium on Theoretical Aspects of Computer Science, pp.396-407, 2006.

N. Alon, I. Newman, A. Shen, G. Tardos, and N. 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, International Conference on Information Theoretic Security, pp.195-210, 2007.

F. Matus, Infinitely many information inequalities, Information Theory, pp.41-44, 2007.

F. Matú?, Adhesivity of polymatroids, Discrete Mathematics, vol.307, issue.21, pp.2464-2477, 2007.

A. D. Smith, Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes, Proceedings of the eighteenth annual ACM-SIAM Symposium on Discrete algorithms, Citeseer, vol.7, pp.395-404, 2007.

B. Durand, L. A. Levin, and A. Shen, Complex tilings, The Journal of Symbolic Logic, vol.73, pp.593-613, 2008.

, Complex tilings, The Journal of Symbolic Logic, vol.73, issue.2, pp.593-613, 2008.

M. Li and P. Vitanyi, An introduction to Kolmogorov complexity and its applications, 1993.

N. Ollinger, Two-by-two substitution systems and the undecidability of the domino problem, Conference on Computability in Europe, pp.476-485, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00204625

A. Ballier, Propriétés structurelles, combinatoires et logiques des pavages, 2009.

V. Guruswami, C. Umans, and S. P. Vadhan, Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, Journal of the ACM, vol.56, issue.4, 2009.

M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Inventiones mathematicae, vol.176, issue.1, p.131, 2009.

A. Ballier and E. Jeandel, Computing (or not) quasi-periodicity functions of tilings, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00542498

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, pp.2011-2038, 2010.

M. Braverman, Poly-logarithmic independence fools bounded-depth boolean circuits, Communications of the ACM, vol.54, issue.4, pp.108-115, 2011.

T. Chan, Recent progresses in characterising information inequalities, Entropy, vol.13, issue.2, pp.379-401, 2011.

I. Csiszar and J. Körner, Information theory: coding theorems for discrete memoryless systems, 2011.

I. Razenshteyn, Common information revisited, 2011.

R. W. Yeung, A first course in information theory, 2012.

N. Aubrun and M. Sablik, Simulation of effective subshifts by twodimensional subshifts of finite type, Acta applicandae mathematicae, vol.126, issue.1, pp.35-63, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01275179

E. Jeandel and P. Vanier, Turing degrees of multidimensional sfts, Theoretical Computer Science, vol.505, pp.81-92, 2013.

T. Kaced, Equivalence of two proof techniques for non-Shannon-type inequalities, Proceedings of IEEE International Symposium on Information Theory (ISIT), pp.236-240, 2013.

B. Bauwens and M. Zimand, Linear list-approximation for short programs (or the power of a few random bits), Proceedings of the 29th IEEE Conference on Computational Complexity, pp.241-247, 2014.

L. Csirmaz, Book inequalities, IEEE Transactions on Information Theory, vol.60, issue.11, pp.6811-6818, 2014.

D. Musatov, Improving the space-bounded version of Muchnik's conditional complexity theorem via "naive" derandomization, Theory of computing systems, vol.55, pp.299-312, 2014.

E. Jeandel and M. Rao, An aperiodic set of 11 wang tiles, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01166053

C. Zinoviadis, Hierarchy and expansiveness in 2D subshifts of finite type, International Conference on Language and Automata Theory and Applications, pp.365-377, 2015.

C. Goodman-strauss, Lots of aperiodic sets of tiles, 2016.

F. Matú? and L. Csirmaz, Entropy region and convolution, IEEE Transactions on Information Theory, vol.62, issue.11, pp.6007-6018, 2016.

C. Zinoviadis, Hierarchy and expansiveness in two-dimensional subshifts of finite type, 2016.

A. Shen, V. Uspensky, and N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01803620

N. Vereshchagin and A. Shen, Algorithmic statistics: forty years later, Computability and Complexity, pp.669-737, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01480627

L. B. Westrick, Seas of squares with sizes from a ? 0 1 set, Israel Journal of Mathematics, vol.222, issue.1, pp.431-462, 2017.

M. Zimand, Kolmogorov complexity version of Slepian-Wolf coding, Proceedings of the annual ACM Symposium on Theory of Computing, pp.22-32, 2017.

M. Zimand, Distributed compression through the lens of algorithmic information theory: a primer, 2017.

B. Bauwens, A. Makhlin, N. Vereshchagin, and M. Zimand, Short lists with short programs in short time, Computational complexity, vol.27, issue.1, pp.31-61, 2018.