70 citations · 115 across the 15 of their papers we have counts for
15 papers
Half-duplex communication complexity with adversary can be less than the classical communication complexity
Mikhail Dektiarev, Nikolay Vereshchagin
Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-d…
On information content in 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 o…
Information disclosure in the framework of Kolmogorov complexity
Nikolay Vereshchagin
We consider the network consisting of three nodes connected by two open channels and . The information present in the node 1 consists of…
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 [Leonid Levin. Laws of Information Conservation (Nongrowth) and Aspects of t…
Algorithmic statistics: forty years later
Nikolai Vereshchagin, Alexander Shen
Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some stat…
Algorithmic statistics revisited
Nikolay Vereshchagin, Alexander Shen
The mission of statistics is to provide adequate statistical hypotheses (models) for observed data. But what is an "adequate" model? To answer this question, one needs to use the n…