### Article

## A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem

We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type (Formula presented.), i.e., corresponding to the affine Lie algebra (Formula presented.). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. Our formula can be viewed as a weighted sum of exponentials of integer points in a certain infinite-dimensional convex polyhedron. We derive a weighted version of Brion’s theorem and then apply it to our polyhedron to prove the formula. © 2016 Springer International Publishing

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string *x* is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of *x*. Further we will show how it can be used for list decoding from erasing and prove that Symmetry of Information fails for total conditional complexity.

Looking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why? The answer is provided by algorithmic information theory: because the sequence is compressible, that is, it has small complexity or, equivalently, can be produced by a short program. This idea, going back to Solomonoff, Kolmogorov, Chaitin, Levin, and others, is now the starting point of algorithmic information theory. The first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part covers some recent work done by participants of the “Kolmogorov seminar” in Moscow (started by Kolmogorov himself in the 1980s) and their colleagues. This book contains numerous exercises (embedded in the text) that will help readers to grasp the material.

In algorithmic statistics quality of a statistical hypothesis (a model) P for a data x is measured by two parameters: Kolmogorov complexity of the hypothesis and the probability P(x). A class of models SijSij that are the best at this point of view, were discovered. However these models are too abstract. To restrict the class of hypotheses for a data, Vereshchaginintroduced a notion of a strong model for it. An object is called normal if it can be explained by using strong models not worse than without this restriction. In this paper we show that there are “many types” of normal strings. Our second result states that there is a normal object x such that all models SijSij are not strong for x. Our last result states that every best fit strong model for a normal object is again a normal object.

Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K can also be used in a similar way: a sequence is 2-random if and only if it has infinitely many initial segments with O(1)-maximal prefix complexity (which is n + K (n) for strings of length n). The known proofs of these results are quite involved; in this paper we provide simple direct proofs for both of them. In [16] Miller also gave a quantitative version of the first result: the 0'-randomness deficiency of a sequence {\omega} equals lim inf [n - C ({\omega}1 . . . {\omega}n)] + O(1). (Our simplified proof can also be used to prove this.) We show (and this seems to be a new result) that a similar quantitative result is also true for prefix complexity: 0'-randomness deficiency equals lim inf [n + K (n) -- K ({\omega}1 . . . {\omega}n)] + O(1). Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs (PDF Download Available). Available from: http://www.researchgate.net/publication/258082399_Prefix_and_plain_Kolmogorov_complexity_characterizations_of_2-randomness_simple_proofs [accessed Oct 20, 2015].

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha- y gin. Randomized Individual Communication Complexity. IEEE Con- ference on Computational Complexity 2008: 321-331] considered com- munication complexity of the following problem. Alice has a bi- nary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(x|y) of x conditional to y. It is easy to show that deterministic communica- tion complexity of approximating C(x|y) with precision α is at least n − 2α − O(1). The above referenced paper asks what is random- ized communication complexity of this problem and shows that for r- round randomized protocols its communication complexity is at least Ω((n/α)1/r ). In this paper, for some positive ε, we show the lower bound 0.99n for (worst case) communication length of any random- ized protocol that with probability at least 0.01 approximates C(x|y) with precision εn for all input pairs.