### 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

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.