113 2.5.2 Embedding an infinite sequence in tiling and enforcing the non-computability of every configuration, p.117 ,
119 2.6.1 Preliminary remarks: Supplementary constraints that can be imposed on a self-simulating tiling ,
,
, , p.126
, On the subdynamics of co-dimension 1 for self-simulating SFTs, p.128
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
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
Conditional Information Inequalities and Combinatorial Application, IEEE Transactions on Information Theory, vol.64, pp.3610-3615, 2018. ,
Topological Arguments for Kolmogorov Complexity, Theory of Computing Systems, vol.56, pp.513-526, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01165095
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
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
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
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
Variations on Muchnik's Conditional Complexity Theorem. Theory of Computing Systems, vol.49, pp.227-245, 2011. ,
Stability of properties of Kolmogorov complexity under relativization, Problems of Information Transmission, vol.46, issue.1, pp.38-61, 2010. ,
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. ,
Resource Bounded Symmetry of Information Revisited, Theoretical Computer Science, vol.345, issue.2-3, pp.386-405, 2005. ,
A Criterion of Extractability of Mutual Information for a Triple of strings, Problems of Information Transmission, vol.39, issue.1, pp.148-157, 2003. ,
A New Class of non Shannon type inequalities for Entropies, Communications in Information and Systems, pp.147-166, 2002. ,
, (version préliminaire dans Proc. of 15th Annual IEEE Conference on Computational Complexity, vol.271, pp.111-123, 2002.
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. ,
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. ,
Pairs of Words with Nonmaterializable Mutual Information, Problems of Information Transmission, vol.36, issue.1, pp.1-18, 2000. ,
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
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
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.
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
Quasiperiodicity and Non-computability in ,
URL : https://hal.archives-ouvertes.fr/lirmm-01165314
, Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS) (2015), Part 1, pp.218-230
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
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
, Lecture Notes in Computer Science, vol.6651, pp.50-63, 2011.
High complexity tilings with sparse errors, Proc. of 36th International Colloquium on Automata, Languages, and Programming (ICALP) 1, pp.403-414, 2009. ,
Variations on Muchnik's Conditional Complexity Theorem, Proc. 4th International Computer Science Symposium in Russia (CSR), pp.250-262, 2009. ,
Fixed Point and Aperiodic Tilings, Proc. 12th International Conference on Developments in Language Theory (DLT) ,
URL : https://hal.archives-ouvertes.fr/hal-00256364
, , pp.537-548, 2008.
A Random Oracle Does Not Help Extract the Mutual Information, Proc. 33rd International Symposium Mathematical Foundations of Computer Science (MFCS), pp.527-538, 2008. ,
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.
On Polynomially Time Bounded Symmetry of Information, Proc. 29th Symposium on the Mathematical Foundations of Computer Science (MFCS), pp.463-475, 2004. ,
Extracting the Mutual Information for a Triple of Binary Strings, Proc. 18th Annual IEEE Conference on Computational Complexity (CCC), pp.221-229, 2003. ,
Combinatorial Interpretation of Kolmogorov Complexity, Proc. 15th Annual IEEE Conference on Computational Complexity (CCC), pp.131-138, 2000. ,
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.
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
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
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
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. ,
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
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
On stability of computations by cellular automata, Proc. European Conf. Compl. Syst, 2005. ,
,
Notes on Coding Theory, Russian) MCCME Publishers, 2011. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01486509
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
The expressiveness of quasiperiodic and minimal shifts of finite type, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01702549
Transmission of information, Bell Labs Technical Journal, vol.7, issue.3, pp.535-563, 1928. ,
Communication theory of secrecy systems, Bell Sys. Tech. Jour, vol.28, pp.623-656, 1948. ,
Three approaches to the quantitative definition of information, Problems Inform. Transmission, vol.1, issue.1, pp.1-7, 1965. ,
The undecidability of the domino problem, vol.66, 1966. ,
Two-tape simulation of multitape turing machines, Journal of the ACM, vol.13, issue.4, pp.533-546, 1966. ,
The definition of random sequences, Information and Control, vol.9, pp.602-619, 1966. ,
Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol.13, issue.7, pp.422-426, 1970. ,
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. ,
Undecidability and nonperiodicity for tilings of the plane, Inventiones mathematicae, vol.12, issue.3, pp.177-209, 1971. ,
The complexity of an optimal non-blocking commutation scheme without reorganization, Problems of Information Transmission, vol.9, issue.1, pp.84-87, 1973. ,
Common information is far less than mutual information, Probl. Control Inf. Theory, vol.2, issue.2, pp.149-162, 1973. ,
On the complexity of a concentrator, 7th International Telegraffic Conference, Citeseer, vol.4, pp.1-318, 1973. ,
Noiseless coding of correlated information sources, IEEE Transactions on Information Theory, vol.19, issue.4, pp.471-480, 1973. ,
On common information and related characteristics of correlated information sources, Preprint. Presented at the 7th Prague Conference on Information Theory, 1974. ,
Nonrecursive tilings of the plane. I, The Journal of Symbolic Logic, vol.39, issue.2, pp.283-285, 1974. ,
Nonrecursive tilings of the plane. II, The Journal of Symbolic Logic, vol.39, issue.2, pp.286-294, 1974. ,
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. ,
A theory of program size formally identical to information theory, Journal of the ACM, vol.22, issue.3, pp.329-340, 1975. ,
Talk at the seminar at moscow state university mathematics department (logic division), 1981. ,
Dominoes are forever, 1983. ,
The concept of (?, ?)-stochasticity in the Kolmogorov sense, and its properties, Soviet Math. Dokl, vol.28, pp.295-299, 1983. ,
Storing a sparse table with 0 (1) worst case access time, Journal of the ACM, vol.31, issue.3, pp.538-544, 1984. ,
Some intersection theorems for ordered sets and graphs, Journal of Combinatorial Theory, Series A, vol.43, issue.1, pp.23-37, 1986. ,
Reliable computation with cellular automata, Journal of Computer and System Sciences, vol.32, issue.1, pp.15-78, 1986. ,
, Tilings and patterns, 1987.
Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, pp.367-376, 1988. ,
, Lecture notes on descriptional complexity and randomness, 1988.
Local rules for quasicrystals, Communications in mathematical physics, vol.119, issue.4, pp.627-666, 1988. ,
Pseudorandom generators for space-bounded computation, Combinatorica, vol.12, issue.4, pp.449-461, 1992. ,
Common randomness in information theory and cryptography-I: secret sharing, IEEE Trans. Information Theory, vol.39, issue.4, pp.1121-1132, 1993. ,
Secret key agreement by public discussion from common information, IEEE Trans. Information Theory, vol.39, issue.3, pp.733-742, 1993. ,
Hardness vs randomness, Journal of computer and System Sciences, vol.49, issue.2, pp.149-167, 1994. ,
Projections of bodies and hereditary properties of hypergraphs, Bulletin of the London Mathematical Society, vol.27, issue.5, pp.417-424, 1995. ,
Eigenvalues and expansion of regular graphs, Journal of the ACM, vol.42, issue.5, pp.1091-1106, 1995. ,
Conditional independences among four random variables ii, Combinatorics, Probability and Computing, vol.4, issue.4, pp.407-417, 1995. ,
An aperiodic set of 13 wang tiles, Discrete Mathematics, vol.160, issue.1-3, pp.245-251, 1996. ,
A small aperiodic set of wang tiles, Discrete Mathematics, vol.160, issue.1-3, pp.259-264, 1996. ,
Theory of self-reproducing automata, 1996. ,
The classical decision problem, 1997. ,
, Communication complexity. Cambridge, 1997.
A non-Shannon-type conditional inequality of information quantities, IEEE Transactions on Information Theory, vol.43, issue.6, pp.1982-1986, 1997. ,
Information distance, IEEE Transactions on information theory, vol.44, issue.4, pp.1407-1423, 1998. ,
On common information, Theor. Comput. Sci, vol.207, pp.319-328, 1998. ,
On characterization of entropy function via information inequalities, IEEE Transactions on Information Theory, vol.44, issue.4, pp.1440-1452, 1998. ,
Membership in constant time and almostminimum space, SIAM Journal on Computing, vol.28, issue.5, pp.1627-1640, 1999. ,
Tilings and quasiperiodicity, Theoretical Computer Science, vol.221, issue.1-2, pp.61-75, 1999. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01165314
Constructions of near-optimal extractors using pseudo-random generators, Proceedings of the 30th ACM Symposium on Theory of Computing, pp.141-148, 1999. ,
Bounds for dispersers, extractors, and depth-two superconcentrators, SIAM Journal on Discrete Mathematics, vol.13, issue.1, pp.2-24, 2000. ,
Resource-bounded Kolmogorov complexity revisited, SIAM Journal on Computing, vol.31, issue.3, pp.887-905, 2001. ,
A reader's guide to gacs's "positive rates" paper, Journal of Statistical Physics, vol.103, issue.1-2, pp.1-44, 2001. ,
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.
Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.143-152, 2001. ,
Are bitvectors optimal?, SIAM Journal on Computing, vol.31, issue.6, pp.1723-1744, 2002. ,
Conditional complexity and codes, Theor. Comput. Sci, vol.271, issue.1-2, pp.97-109, 2002. ,
Storing information with extractors, Information Processing Letters, vol.83, issue.5, pp.267-274, 2002. ,
Cuckoo hashing: further analysis, Information Processing Letters, vol.86, issue.4, pp.215-219, 2003. ,
A note on Kolmogorov complexity and entropy, vol.16, pp.1129-1130, 2003. ,
Secrecy capacities for multiple terminals, IEEE Trans. Information Theory, vol.50, issue.12, pp.3047-3061, 2004. ,
Cuckoo hashing, Journal of Algorithms, vol.51, issue.2, pp.122-144, 2004. ,
Language compression and pseudorandom generators, Computational Complexity, vol.14, issue.3, pp.228-255, 2005. ,
Local rules and global order, or aperiodic tilings, The Mathematical Intelligencer, vol.27, pp.64-68, 2005. ,
Aperiodic tilings: breaking translational symmetry, The Computer Journal, vol.48, issue.6, pp.642-645, 2005. ,
On common information and related characteristics of correlated information sources, General Theory of Information Transfer and Combinatorics, pp.664-677, 2006. ,
, Elements of information theory, 2006.
Expander graphs and their applications, Bulletin of the American Mathematical Society, vol.43, issue.4, pp.439-561, 2006. ,
Extracting randomness via repeated condensing, SIAM Journal on Computing, vol.35, issue.5, pp.1185-1209, 2006. ,
Forbidden substrings, Kolmogorov complexity and almost periodic sequences, Annual Symposium on Theoretical Aspects of Computer Science, pp.396-407, 2006. ,
Partitioning multi-dimensional sets in a small number of "uniform" parts, European Journal of Combinatorics, vol.28, issue.1, pp.134-144, 2007. ,
Cryptographic security of individual instances, International Conference on Information Theoretic Security, pp.195-210, 2007. ,
Infinitely many information inequalities, Information Theory, pp.41-44, 2007. ,
Adhesivity of polymatroids, Discrete Mathematics, vol.307, issue.21, pp.2464-2477, 2007. ,
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. ,
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.
An introduction to Kolmogorov complexity and its applications, 1993. ,
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
Propriétés structurelles, combinatoires et logiques des pavages, 2009. ,
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, Journal of the ACM, vol.56, issue.4, 2009. ,
On the dynamics and recursive properties of multidimensional symbolic systems, Inventiones mathematicae, vol.176, issue.1, p.131, 2009. ,
Computing (or not) quasi-periodicity functions of tilings, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00542498
A characterization of the entropies of multidimensional shifts of finite type, pp.2011-2038, 2010. ,
Poly-logarithmic independence fools bounded-depth boolean circuits, Communications of the ACM, vol.54, issue.4, pp.108-115, 2011. ,
Recent progresses in characterising information inequalities, Entropy, vol.13, issue.2, pp.379-401, 2011. ,
Information theory: coding theorems for discrete memoryless systems, 2011. ,
Common information revisited, 2011. ,
A first course in information theory, 2012. ,
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
Turing degrees of multidimensional sfts, Theoretical Computer Science, vol.505, pp.81-92, 2013. ,
Equivalence of two proof techniques for non-Shannon-type inequalities, Proceedings of IEEE International Symposium on Information Theory (ISIT), pp.236-240, 2013. ,
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. ,
Book inequalities, IEEE Transactions on Information Theory, vol.60, issue.11, pp.6811-6818, 2014. ,
Improving the space-bounded version of Muchnik's conditional complexity theorem via "naive" derandomization, Theory of computing systems, vol.55, pp.299-312, 2014. ,
An aperiodic set of 11 wang tiles, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01166053
Hierarchy and expansiveness in 2D subshifts of finite type, International Conference on Language and Automata Theory and Applications, pp.365-377, 2015. ,
Lots of aperiodic sets of tiles, 2016. ,
Entropy region and convolution, IEEE Transactions on Information Theory, vol.62, issue.11, pp.6007-6018, 2016. ,
Hierarchy and expansiveness in two-dimensional subshifts of finite type, 2016. ,
Kolmogorov complexity and algorithmic randomness, 2017. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01803620
Algorithmic statistics: forty years later, Computability and Complexity, pp.669-737, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01480627
Seas of squares with sizes from a ? 0 1 set, Israel Journal of Mathematics, vol.222, issue.1, pp.431-462, 2017. ,
Kolmogorov complexity version of Slepian-Wolf coding, Proceedings of the annual ACM Symposium on Theory of Computing, pp.22-32, 2017. ,
Distributed compression through the lens of algorithmic information theory: a primer, 2017. ,
Short lists with short programs in short time, Computational complexity, vol.27, issue.1, pp.31-61, 2018. ,