Randomness, Information, Complexity

How can we measure the "value'' of the information contained in a binary string? And how can we distinguish between useful information and useless one? In connection with these questions, a variety of different notions were proposed, including Bennett’s logical depth, Koppel’s sophistication, and Gell-Mann and Lloyd’s effective complexity.
In connection with infinite binary sequences, logical depth has also been applied for investigating the relation between the information content of a sequence and its computational power and usefulness. Over the last decade, these investigations received some attention and several new results were obtained.  We give an introduction to this active and promising research area and review its state of the art.

Randomness spaces were introduced by Hertling and Weihrauch in 1998 as a setting for defining randomness in general topological spaces. Afterwards, Calude et al. translated the technique to full shift spaces and analyzed the randomness behavior of cellular automata. Another approach to the study of randomness in dynamical systems, an in particular of cellular automata has been proposed by Cervelle, Durand and Formenti in 2001. In this talk we compare both approaches and conclude with a series of open questions.

We consider computations of a Turing machine subjected to noise. In every step, the action (the new state and the new content of the observed cell, the direction of the head movement) can differ from that prescribed by the transition function with a small probability (independently of previous such events). We construct a universal Turing machine that for a low enough (constant) noise probability performs arbitrarily large computations. For this unavoidably, the input needs to be encoded by a code depending on its size. The work uses a technique familiar from reliable cellular automata, complemented by some new ideas. The talk will focus on the central concept: a hierarchy of generalized Turing machines, each one simulating a more reliable one.
This is joint work with Ilir Capuni.

A two-dimensional configuration is a coloring of the infinite grid ℤ² using a finite number of colors. For a finite subset D of ℤ², the D-patterns of a configuration are the patterns of shape D that appear in the configuration. The number of distinct D-patterns of a configuration is a natural measure of its complexity. We consider low-complexity configurations where the number of distinct D-patterns is at most |D|, the size of the shape. We use algebraic tools to study periodicity of such configurations. In the case D is a rectangle, we prove that a low-complexity configuration must contain arbitrarily large periodic patches. This implies an algorithm to determine if a given collection of mn rectangular patterns of size m times n admit a configuration containing only these patterns. (Without the complexity bound the question is the well-known undecidable domino problem.) We also show, for an arbitrary shape D, that a low-complexity configuration must be periodic if it comes from the well-known Ledrappier subshift, or from a wide family of other similar algebraic subshifts.

Approximate majority is a problem of computing majority function with the promise that the fraction of ones is bounded by a positive constant from ½. It turns out that there is an explicit depth-3 polynomial size monotone Boolean circuit for approximate majority (Viola, 2007).
We notice that the corresponding Karchmer---Wigderson game is equivalent to the following problem which we call Inevitable Repetitions: each of two parties receives a subset of {1,…,n} with the promise that the sum of their sizes is (1+Ω(1))n. The goal is to output any common element. We generalize a result of Viola by considering a multiparty version of Inevitable Repetitions. Namely, when the number of parties is constant, we construct an explicit O(1)-round O(log n)-communication protocol for our problem. For two parties our protocol runs in 3 rounds which gives an alternative proof of a result of Viola.
We also provide a tight lower bound for a natural analogue of Inevitable Repetition problem in the Finite Automata world. Finally, we notice that some ideas used in our proofs allow us to save a polylog-factor from the Sipser-Lautemann theorem.

Sasha Shen’s work comprises several cases where he was able to simplify proofs of existing results. We will review three examples of such simplifications, relating to the result that IP is equal PSPACE due to Shamir, to the characterization of Martin-Löf randomness via plain Kolmogorov complexity of initial segments due to Miller and Yu, subsequent to a preliminary result by Gács, and to the fact that a sequences computes a diagonally nonrecursive function if and only if the sequence is autocomplex due to Kjos-Hanssen, Merkle and Stephan. We present full proofs and some related material for the second and third example. For the second example, we give a slightly further simplified, yet unpublished proof. In connection with the third example, we review the classical result that computing a diagonally nonrecursive and a fixed-point free function is equally difficult, which yields a short proof for the recursion theorem that is similar to but more intuitive than the usual textbook proof.
Recall that a function g is diagonally nonrecursive in case g(e) differs for all e from the potentially undefined value φₑ(e), where φ₀, φ₁, … is an appropriate numbering of all partial recursive functions. Recall further that a sequence A is autocomplex if there is an A-computable function h that is a lower bound for the prefix-free Kolmogorov complexity of the initial segments of A in the sense that h(n)≤K(A(0)…A(n)) for all n.

Consider a binary string x of length n whose Kolmogorov complexity is αn for some α<1. We want to increase the complexity of x by changing a small fraction of bits in x. This is always possible: Buhrman, Fortnow, Newman and Vereshchagin showed [1] that the increase can be at least δn for large n (where δ is some positive number that depends on α and the allowed fraction of changed bits).
We consider a related question: what happens with the complexity of x when we randomly change a small fraction of the bits (changing each bit independently with some probability τ)? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change. We note that the amount of the increase depends on x (strings of the same complexity could behave differently), and give exact lower and upper bounds for this increase (with o(n) precision).
The proof uses the combinatorial and probabilistic technique that goes back to Ahlswede, Gács and Körner [2]. For the reader's convenience (and also because we need a slightly stronger statement) we provide a simplified exposition of this technique, so the paper is self-contained.
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 [3] and show that for every sequence ω of dimension α there exists a strongly α-random sequence ω' such that the Besicovitch distance between ω and ω' is 0.
This is joint work with Alexander Shen.
[1] Rudolf Ahlswede, Peter Gács, and János Körner. Bounds on conditional probabilities with applications in multi-user communication. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 34(2):157–177, 1976.
[2] Harry Buhrman, Lance Fortnow, Ilan Newman, and Nikolai K. Vereshchagin. Increasing Kolmogorov complexity. In Volker Diekert and Bruno Durand, editors, STACS 2005, Stuttgart, Germany, February 24-26, volume 3404 of Lecture Notes in Computer Science, pages 412–421. Springer, 2005.
[3] Noam Greenberg, Joseph S. Miller, Alexander Shen, and Linda Brown Westrick. Dimension 1 sequences are close to randoms. Theoretical Computer Science, 705:99–112, 2018.

We present a structural lemma for deterministic context free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions. Pumping lemmata claim that for each word in a sequence there is a decomposition of some form, but the structural lemmata allow to fix not only a sequence of words, but also the decomposition in advance. So it is much easier to apply, than a kind of pumping lemmata.
The relation of the lemma with known structural lemmata for DCFL class is as follows. The lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by M. Li and P. Vitányi in 1995 and corrected by O. Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes. We also show the connection between S. Yu's pumping lemma for DCFL in 1989 and the technique presented by J. Shallit in the book "A Second Course in Formal Languages and Automata Theory".

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the complexity of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play. For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height n admits a strategy of width sub-exponential in logn.) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (2016).
This is joint work with Dmitry Chistikov.