Algorithmic Measures of Information for Tuples of Words and for Patterns in Multidimensional Shifts of Finite Type

No abstract is available for this paper.

• Publication year

  2018

• Venue

  Unknown venue

• Publication date

  Unknown publication date

• Fields of study

  Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Expressive Power of Quasiperiodic SFT

  2017cited by this paper
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES

  2017cited by this paper
• An Operational Characterization of Mutual Information in Algorithmic Information Theory

  2017cited by this paper
• Distributed compression through the lens of algorithmic information theory: a primer

  2017cited by this paper
• Algorithmic statistics: forty years later

  2016cited by this paper
• Hierarchy and Expansiveness in Two-Dimensional Subshifts of Finite Type

  2016cited by this paper
• Communication Complexity

  2016cited by this paper
• Lots of aperiodic sets of tiles

  2016cited by this paper
• SEAS OF SQUARES WITH SIZES FROM A Π1 SET

  2016cited by this paper
• Conditional Information Inequalities and Combinatorial Applications

  2015cited by this paper
• Kolmogorov complexity version of Slepian-Wolf coding

  2015cited by this paper
• Hierarchy and Expansiveness in 2D Subshifts of Finite Type

  2015cited by this paper
• Quasiperiodicity and Non-computability in Tilings

  2015cited by this paper
• On the Combinatorial Version of the Slepian–Wolf Problem

  2015cited by this paper
• Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem

  2015cited by this paper
• Linear List-Approximation for Short Programs (or the Power of a Few Random Bits)

  2013cited by this paper
• Book Inequalities

  2013cited by this paper
• The axiomatic power of Kolmogorov complexity

  2013cited by this paper
• Simulation of Effective Subshifts by Two-dimensional Subshifts of Finite Type

  2013cited by this paper
• Short lists with short programs in short time

  2013cited by this paper
• KOLMOGOROV COMPLEXITY AND ALGORITHMIC RANDOMNESS

  2013cited by this paper
• Entropy Region and Convolution

  2013cited by this paper
• Equivalence of two proof techniques for non-shannon-type inequalities

  2013cited by this paper
• On the non-robustness of essentially conditional information inequalities

  2012cited by this paper
• Conditional Information Inequalities for Entropic and Almost Entropic Points

  2012cited by this paper
• Topological Arguments for Kolmogorov Complexity

  2012cited by this paper
• On essentially conditional information inequalities

  2011cited by this paper
• Turing degrees of multidimensional SFTs

  2011cited by this paper
• Poly-logarithmic independence fools bounded-depth boolean circuits

  2011cited by this paper
• Local rules and global order

  2011cited by this paper
• Common information revisited

  2011cited by this paper
• Information Theory: Multi-terminal systems

  2011cited by this paper
• Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error

  2011cited by this paper
• Recent Progresses in Characterising Information Inequalities

  2011cited by this paper
• Effective closed subshifts in 1D can be implemented in 2D

  2010cited by this paper
• Stability of properties of Kolmogorov complexity under relativization

  2010cited by this paper
• Computing (or not) Quasi-periodicity Functions of Tilings

  2010cited by this paper
• Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

  2010cited by this paper
• On the dynamics and recursive properties of multidimensional symbolic systems

  2009influential reference
• Fixed-point tile sets and their applications

  2009cited by this paper
• Variations on Muchnik’s Conditional Complexity Theorem

  2009cited by this paper
• High Complexity Tilings with Sparse Errors

  2009cited by this paper
• Upper semilattice of binary strings with the relation “ x is simple conditional to y ”

  2009cited by this paper
• Propriétés structurelles, combinatoires et logiques des pavages. (Stuctural, combinatorics and logical properties of tilings)

  2009cited by this paper
• Cryptographic Security of Individual Instances

  2009cited by this paper
• Sparse sets

  2008cited by this paper
• Fixed Point and Aperiodic Tilings

  2008cited by this paper
• A Random Oracle Does Not Help Extract the Mutual Information

  2008cited by this paper
• Two-by-Two Substitution Systems and the Undecidability of the Domino Problem

  2008cited by this paper
• Infinitely Many Information Inequalities

  2007influential reference
• Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

  2007cited by this paper
• Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes

  2007cited by this paper
• Adhesivity of polymatroids

  2007cited by this paper
• Partitioning multi-dimensional sets in a small number of "uniform" parts

  2007cited by this paper
• A Characterization of the Entropies of Multidimensional Shifts of Finite Type

  2007cited by this paper
• Expander Graphs and their Applications

  2006cited by this paper
• Reliable Computations Based on Locally Decodable Codes

  2006cited by this paper
• Appendix: On Common Information and Related Characteristics of Correlated Information Sources

  2006cited by this paper
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences

  2006cited by this paper
• Resource bounded symmetry of information revisited

  2005cited by this paper
• Local rules and global order, or aperiodic tilings

  2005cited by this paper
• Secrecy capacities for multiple terminals

  2004cited by this paper
• Aperiodic Tilings: Breaking Translational Symmetry

  2004cited by this paper
• On Polynomially Time Bounded Symmetry of Information

  2004cited by this paper
• Language compression and pseudorandom generators

  2004cited by this paper
• A note on Kolmogorov complexity and entropy

  2003cited by this paper
• Notes on Coding Theory

  2003cited by this paper
• Extracting the mutual information for a triple of binary strings

  2003cited by this paper
• Cuckoo hashing: Further analysis

  2003cited by this paper
• A Criterion for Extractability of Mutual Information for a Triple of Strings

  2003cited by this paper
• A new class of non-Shannon-type inequalities for entropies

  2002cited by this paper
• Conditional complexity and codes

  2002cited by this paper
• A First Course in Information Theory

  2002influential reference
• Upper semi-lattice of binary strings with the relation "x is simple conditional to y"

  2002cited by this paper
• Storing information with extractors

  2002cited by this paper
• Loss-less condensers, unbalanced expanders, and extractors

  2001cited by this paper
• LOW REDUNDANCY IN STATIC DICTIONARIES WITH CONSTANT QUERY TIME

  2001cited by this paper
• Complex tilings

  2001cited by this paper
• Cuckoo Hashing

  2001cited by this paper
• A Reader's Guide to Gacs's “Positive Rates” Paper

  2001cited by this paper
• On the cell probe complexity of membership and perfect hashing

  2001cited by this paper
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators

  2000cited by this paper
• Combinatorial interpretation of Kolmogorov complexity

  2000cited by this paper
• Are bitvectors optimal?

  2000influential reference
• Inequalities for Shannon Entropy and Kolmogorov Complexity

  2000cited by this paper
• Extracting randomness via repeated condensing

  2000cited by this paper
• Membership in Constant Time and Almost-Minimum Space

  1999cited by this paper
• On characterization of entropy function via information inequalities

  1998influential reference
• Information Distance

  1998cited by this paper
• On Common Information

  1998cited by this paper
• Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

  1998cited by this paper
• Tilings and Quasiperiodicity

  1997cited by this paper
• The Classical Decision Problem

  1997cited by this paper
• Resource-Bounded Kolmogorov Complexity Revisited

  1997cited by this paper
• A non-Shannon-type conditional inequality of information quantities

  1997cited by this paper
• Inequalities for Shannon entropies and Kolmogorov complexities

  1997cited by this paper
• An aperiodic set of 13 Wang tiles

  1996cited by this paper
• A small aperiodic set of Wang tiles

  1996cited by this paper
• Conditional Independences among Four Random Variables II

  1995cited by this paper
• Eigenvalues and expansion of regular graphs

  1995cited by this paper

• No citing papers are available for this paper.