Author name cluster

Nikolay Vereshchagin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

I&C Journal 2026 Journal Article

Total conditional complexity of certain objects

Nikolay Vereshchagin

The fine approach to measure information dependence is based on the total conditional complexity CT ( y | x ), which is defined as the minimal length of a total program that outputs y on the input x. It is known that the total conditional complexity can be much larger than the plain conditional complexity. Such strings x, y are defined by means of a diagonal argument and are not otherwise interesting. In this paper we investigate whether this happens also for some natural objects having some other interesting properties. More specifically, we consider the following objects: the number of strings of complexity less than n and the lex first string of length n and complexity ⩾n. It is known that they have negligible mutual conditional complexities. In this paper we prove that their mutual total conditional complexities may be large. This is the first example of interesting objects whose plain conditional complexity is much less than the total one.

Details DOI

TCS Journal 2023 Journal Article

Information disclosure in the framework of Kolmogorov complexity

Nikolay Vereshchagin

We consider the network consisting of three nodes 1, 2, 3 connected by two open channels 1 → 2 and 1 → 3. The information present in the node 1 consists of four strings x, y, z, w. The nodes 2, 3 know x, w and need to know y, z, respectively. We want to arrange transmission of information over the channels so that both nodes 2 and 3 learn what they need and the disclosure of information is as small as possible. By information disclosure we mean the amount of information in the strings transmitted through channels about x, y, z, w (or about x, w ). We are also interested in whether it is possible to minimize the disclosure of information and simultaneously minimize the length of words transferred through the channels.

Details DOI

TCS Journal 2021 Journal Article

Proofs of conservation inequalities for Levin's notion of mutual information of 1974

Nikolay Vereshchagin

In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in Levin (1974) [6]. The respective information conservation inequalities were stated in that paper without proofs. Later some proofs appeared in the literature, however no proof of the probabilistic conservation inequality has been published yet. In this paper we prove that inequality and for the sake of completeness we present also short proofs of other properties of the said notion.

Details DOI

TCS Journal 2020 Journal Article

Descriptive complexity of computable sequences revisited

Nikolay Vereshchagin

The purpose of this paper is to answer two questions left open in Durand et al. (2001) [2]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence α: C 0 ′ ( α ), defined as the minimal length of a program with oracle 0′ that prints α, and M ∞ ( α ), defined as lim sup C ( α 1: n | n ), where α 1: n denotes the length-n prefix of α and C ( x | y ) stands for conditional Kolmogorov complexity. We show that C 0 ′ ( α ) ⩽ M ∞ ( α ) + O ( 1 ) and M ∞ ( α ) is not bounded by any computable function of C 0 ′ ( α ), even on the domain of computable sequences.

Details DOI