27 Open Problems in Kolmogorov Complexity
The paper proposes open problems in classical Kolmogorov complexity. Each problem is presented with background information and thus the article also surveys some recent studies in the area.
Source author record
Andrei Romashchenko
Andrei Romashchenko appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
19works
11topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
19 published item(s)
preprint2022arXiv
Clustering with Respect to the Information Distance
We discuss the notion of a dense cluster with respect to the information distance and prove that all such clusters have an extractable core that represents the mutual information shared by the objects in the cluster.
0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv
Inequalities for space-bounded Kolmogorov complexity
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (Hammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998--2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpré (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpré's result with a tighter space bound, using Sipser's trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead.
0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
We suggest necessary conditions of soficness of multidimensional shifts formulated in termsof resource-bounded Kolmogorov complexity. Using this technique we provide examples ofeffective and non-sofic shifts on $\mathbb{Z}^2$ with very low block complexity: the number of globallyadmissible patterns of size $n\times n$ grows only as a polynomial in $n$. We also show that moreconventional proofs of non-soficness for multi-dimensional effective shifts can be expressed interms of Kolmogorov complexity with unbounded computational resources.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Coding in the fork network in the framework of Kolmogorov complexity
Many statements from the classic information theory (the theory of Shannon's entropy) have natural counterparts in the algorithmic information theory (in the framework of Kolmogorov complexity). In this paper we discuss one simple instance of the parallelism between Shannon's and Kolmogorov's theories: we prove in the setting of Kolmogorov complexity a version of Wolf's characterization of admissible rates for the fork network.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Quasiperiodicity and non-computability in tilings
We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove existence of a tile set that accepts only quasiperiodic and non-recursive tilings. Our construction is based on the fixed point construction; we improve this general technique and make it enforce the property of local regularity of tilings needed for quasiperiodicity. We prove also a stronger result: any effectively closed set can be recursively transformed into a tile set so that the Turing degrees of the resulted tilings consists exactly of the upper cone based on the Turing degrees of the later.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Topological arguments for Kolmogorov complexity
We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial algorithmic properties.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Fixed-point tile sets and their applications
An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals). We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. This construction it rather flexible, so it can be used in many ways: we show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, characterize effectively closed 1D subshift it terms of 2D shifts of finite type (improvement of a result by M. Hochman), to construct a tile set which has only complex tilings, and to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. For the latter we develop a hierarchical classification of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: there exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Conditional Information Inequalities for Entropic and Almost Entropic Points
We study conditional linear information inequalities, i.e., linear inequalities for Shannon entropy that hold for distributions whose entropies meet some linear constraints. We prove that some conditional information inequalities cannot be extended to any unconditional linear inequalities. Some of these conditional inequalities hold for almost entropic points, while others do not. We also discuss some counterparts of conditional information inequalities for Kolmogorov complexity.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
The axiomatic power of Kolmogorov complexity
The famous Gödel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T. In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us to prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter, unless NP=PSPACE. We then study the axiomatic power of the statements of type "the Kolmogorov complexity of x exceeds n" in general. They are Π_1 (universally quantified) statements of Peano arithmetic. We show that by adding all true statements of this type, we obtain a theory that proves all true Π_1-statements, and also provide a more detailed classification. In particular, to derive all true Π_1-statements it is sufficient to add one statement of this type for each n (or even for infinitely many n) if strings are chosen in a special way. On the other hand, one may add statements of this type for most x of length n (for every n) and still obtain a weak theory. We also study other logical questions related to "random axioms". Finally, we consider a theory that claims Martin-Löf randomness of a given infinite binary sequence. This claim can be formalized in different ways. We show that different formalizations are closely related but not equivalent, and study their properties.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Conditional and unconditional information inequalities: an algebraic example
We provide a simple example showing that some conditional information inequalities (even in a weak form) cannot be derived from unconditional inequalities.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On the Non-robustness of Essentially Conditional Information Inequalities
We show that two essentially conditional linear inequalities for Shannon's entropies (including the Zhang-Yeung'97 conditional inequality) do not hold for asymptotically entropic points. This means that these inequalities are non-robust in a very strong sense. This result raises the question of the meaning of these inequalities and the validity of their use in practice-oriented applications.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
On essentially conditional information inequalities
In 1997, Z.Zhang and R.W.Yeung found the first example of a conditional information inequality in four variables that is not "Shannon-type". This linear inequality for entropies is called conditional (or constraint) since it holds only under condition that some linear equations are satisfied for the involved entropies. Later, the same authors and other researchers discovered several unconditional information inequalities that do not follow from Shannon's inequalities for entropy. In this paper we show that some non Shannon-type conditional inequalities are "essentially" conditional, i.e., they cannot be extended to any unconditional inequality. We prove one new essentially conditional information inequality for Shannon's entropy and discuss conditional information inequalities for Kolmogorov complexity.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Pseudo-random graphs and bit probe schemes with one-sided error
We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of type "Is x in A?" can be answered very quickly. H.Buhrman, P.B.Miltersen, J.Radhakrishnan, and S.Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of $O(n\log m)$ bits, and requires to read only one randomly chosen bit from the memory to answer a query. The answer is correct with high probability with two-sided errors. In this paper we show that for the same problem there exists a bit-probe scheme with one-sided error that needs space of $O(n\log^2 m+\poly(\log m))$ bits. The difference with the model of Buhrman, Miltersen, Radhakrishnan, and Venkatesh is that we consider a bit-probe scheme with an auxiliary word. This means that in our scheme the memory is split into two parts of different size: the main storage of $O(n\log^2 m)$ bits and a short word of $\log^{O(1)}m$ bits that is pre-computed once for the stored set A and `cached'. To answer a query "Is x in A?" we allow to read the whole cached word and only one bit from the main storage. For some reasonable values of parameters our space bound is better than what can be achieved by any scheme without cached data.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Variations on Muchnik's Conditional Complexity Theorem
Muchnik's theorem about simple conditional descriptions states that for all strings $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. In this paper we present two new proofs of this theorem. The first one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik's theorem for space-bounded Kolmogorov complexity.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
1D Effectively Closed Subshifts and 2D Tilings
Michael Hochman showed that every 1D effectively closed subshift can be simulated by a 3D subshift of finite type and asked whether the same can be done in 2D. It turned out that the answer is positive and necessary tools were already developed in tilings theory. We discuss two alternative approaches: first, developed by N. Aubrun and M. Sablik, goes back to Leonid Levin; the second one, developed by the authors, goes back to Peter Gacs.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Effective closed subshifts in 1D can be implemented in 2D
In this paper we use fixed point tilings to answer a question posed by Michael Hochman and show that every one-dimensional effectively closed subshift can be implemented by a local rule in two dimensions. The proof uses the fixed-point construction of an aperiodic tile set and its extensions.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Fixed Point and Aperiodic Tilings
An aperiodic tile set was first constructed by R.Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals) We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. The flexibility of this construction allows us to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Fixed point theorem and aperiodic tilings
We propose a new simple construction of an aperiodic tile set based on self-referential (fixed point) argument. People often say about some discovery that it appeared "ahead of time", meaning that it could be fully understood only in the context of ideas developed later. For the topic of this note, the construction of an aperiodic tile set based on the fixed-point (self-referential) approach, the situation is exactly the opposite. It should have been found in 1960s when the question about aperiodic tile sets was first asked: all the tools were quite standard and widely used at that time. However, the history had chosen a different path and many nice geometric ad hoc constructions were developed instead (by Berger, Robinson, Penrose, Ammann and many others. In this note we try to correct this error and present a construction that should have been discovered first but seemed to be unnoticed for more that forty years.
0 citations0 reviewsNo code linkedOpen access