research
∙
05/02/2023
Spectral approach to the communication complexity of multi-party key agreement
In multi-party key agreement protocols it is assumed that the parties ar...
share
research
∙
03/28/2022
27 Open Problems in Kolmogorov Complexity
The paper proposes open problems in classical Kolmogorov complexity. Eac...
research
∙
10/04/2021
Clustering with Respect to the Information Distance
We discuss the notion of a dense cluster with respect to the information...
research
∙
10/20/2020
Inequalities for space-bounded Kolmogorov complexity
There is a parallelism between Shannon information theory and algorithmi...
research
∙
04/28/2020
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
It is known that the mutual information, in the sense of Kolmogorov comp...
research
∙
05/01/2019
On a conditional inequality in Kolmogorov complexity and its applications in communication complexity
Romashchenko and Zimand rom-zim:c:mutualinfo have shown that if we parti...
research
∙
01/22/2019
How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma
We discuss linear programming techniques that help to deduce corollaries...
research
∙
05/10/2018
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
We propose necessary conditions of soficness of multidimensional shifts ...
research
∙
02/05/2018
The expressiveness of quasiperiodic and minimal shifts of finite type
We study multidimensional minima and quasiperiodic shifts of finite type...
research
∙
10/16/2017