This editorial contains Vladimir V’yugin’s short biography and a selective review of his contributions to several areas of mathematics, computer science, and their applications.

In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior ---which we call 'bounded conflicts' condition---under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.

Consider a bit string x of length n and Kolmogorov complexity alpha n (for some alpha<1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [Harry Buhrman et al., 2005]. What happens with the complexity of x when we randomly change each bit independently with some probability tau? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change considered in [Harry Buhrman et al., 2005]. The amount of the increase depends on x (strings of the same complexity could behave differently). We give exact lower and upper bounds for this increase (with o(n) precision). The same technique is used to prove the results about the (effective Hausdorff) dimension of infinite sequences. We show that random change increases the dimension with probability 1, and provide an optimal lower bound for the dimension of the changed sequence. We also improve a result from [Noam Greenberg et al., 2018] and show that for every sequence omega of dimension alpha there exists a strongly alpha-random sequence omega' such that the Besicovitch distance between omega and omega' is 0. The proofs use the combinatorial and probabilistic reformulations of complexity statements and the technique that goes back to Ahlswede, Gács and Körner [Ahlswede et al., 1976].

In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)

A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appear

Abstract Péter Gács showed (Gács 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., $C\left( {C\left( x \right)|x} \right) \ge {\rm{log}}n - {\rm{log}}^{\left( 2 \right)} n - O\left( 1 \right)$ (Here ${\rm{log}}^{\left( 2 \right)} i = {\rm{loglog}}i$.) Following Elena Kalinina (Kalinina 2011), we provide a simple game-based proof of this result; modifying her argument, we get a better (and tight) bound ${\rm{log}}n - O\left( 1 \right)$ We also show the same bound for prefix-free complexity. Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that $|x| - C\left( x \right) \le c$ and $|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - c{\rm{log}}^{\left( 3 \right)} |x|$ In fact, the results of Solovay and Gács are closely related. Using the result above, we provide a short proof for Solovay’s result. We also generalize it by showing that for some c and for all n there are strings x of length n with $n - C\left( x \right) \le c$ and $n + K\left( n \right) - K\left( x \right) \ge K\left( {K\left( n \right)|n} \right) - 3K\left( {K\left( {K\left( n \right)|n} \right)|n} \right) - c.$ We also prove a close upper bound $K\left( {K\left( n \right)|n} \right) + O\left( 1 \right)$ Finally, we provide a direct game proof for Joseph Miller’s generalization (Miller 2006) of the same Solovay’s theorem: if a co-enumerable set (a set with c.e. complement) contains for every length a string of this length, then it contains infinitely many strings x such that $|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - O\left( {{\rm{log}}^{\left( 3 \right)} |x|} \right).$

Abstract We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with Kolmogorov complexity of its (n×n)-squares. We construct tile sets for which this bound is tight: all (n×n)-squares in all tilings have complexity Ω(n). This adds a quantitative angle to classical results on non-recursivity of tilings—that we also develop in terms of Turing degrees of unsolvability.

We study the minimal complexity of tilings of a plane with a given tile set. We note that any tile set admits either no tiling or some tiling with \ooo(n) Kolmogorov complexity of its (n\times n)-squares. We construct tile sets for which this bound is nearly tight: all tilings have complexity >n/r(n), given any unbounded computable monotone r. This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability.

In this paper we construct a structure R that is a "finite version" of the semilattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x/spl les/y means that K(x|)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound O (minimal element) but significant mutual information. (A first example of that kind was constructed by Gacs-Korner (1973) using completely different technique.) We define a notion of "complexity profile" of the pair of elements of R and give (exact) upper and lower bounds for it in a particular case.

The question why and how probability theory can be applied to the real-world phenomena has been discussed for several centuries. When the algorithmic information theory was created, it became possible to discuss these problems in a more specific way. In particular, Li and Vitányi [6], Rissanen [3], Wallace and Dowe [7] have discussed the connection between Kolmogorov (algorithmic) complexity and minimum description length (minimum message length) principle. In this note we try to point out a few simple observations that (we believe) are worth keeping in mind while discussing these topics.

Since the very beginning the notion of complexity of finite objects was considered as an algorithmic counterpart to the notion of Shannon entropy. Kolmogorov's paper (1965) was called "Three approaches to the quantitative definition of information"; Shannon entropy and algorithmic complexity were among these approaches. It was mentioned by Kolmogorov later (1968) that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropies and for Kolmogorov complexities. It turns out that (1) all inequalities that are valid for Kolmogorov complexities, are also valid for Shannon entropies and vice versa; (2) all inequalities that are valid for Shannon entropies, are valid for ranks of finite subsets of linear spaces; (3) the opposite statement is not true: Ingleton's inequality (1971) is valid for ranks but not for Shannon entropies; (4) for some special cases all three classes of inequalities coincide and have simple description. We present an inequality for Kolmogorov complexities that implies Ingleton's inequality for ranks; another application of this inequality is a new simple proof of one of Gacs-Korner's results on common information. The paper investigates connections between linear inequalities that are valid for Shannon entropies and for Kolmogorov complexities.

Lund et al. [1] have proved that PH is contained in IP. Shamir [2] improved this technique and proved that PSPACE = IP. In this note, a slightly simplified version of Shamir's proof is presented, using degree reductions instead of simple QBFs.