Andrei E. Romashchenko

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

2024

Spectral Approach to the Communication Complexity of Multi-Party Key Agreement.

[BibT_eX]

[DOI]

Geoffroy Caillat-Grenier

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Common Information in Well-Mixing Graphs and Applications to Information-Theoretic Cryptography.

[BibT_eX]

[DOI]

Geoffroy Caillat-Grenier

Rustam Zyavgarov

Proceedings of the IEEE Information Theory Workshop, 2024

2022

Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301).

[BibT_eX]

[DOI]

Phokion G. Kolaitis

Milan Studený

Dan Suciu

Tobias Boege

Dagstuhl Reports, July, 2022

Clustering with respect to the information distance.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Inequalities for space-bounded Kolmogorov complexity.

[BibT_eX]

[DOI]

Bruno Bauwens

Péter Gács

Comput., 2022

2021

27 Open Problems in Kolmogorov Complexity.

[BibT_eX]

[DOI]

Marius Zimand

SIGACT News, 2021

2020

Inequalities for space-bounded Kolmogorov complexity.

[BibT_eX]

[DOI]

Péter Gács

CoRR, 2020

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory.

[BibT_eX]

[DOI]

Emirhan Gürpinar

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

On a conditional inequality in Kolmogorov complexity and its applications in communication complexity.

[BibT_eX]

[DOI]

Marius Zimand

CoRR, 2019

Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts.

[BibT_eX]

[DOI]

Julien Destombes

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma.

[BibT_eX]

[DOI]

Emirhan Gürpinar

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

A Conditional Information Inequality and Its Combinatorial Applications.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

On the Combinatorial Version of the Slepian-Wolf Problem.

[BibT_eX]

[DOI]

Daniyar Chumbalov

IEEE Trans. Inf. Theory, 2018

The expressiveness of quasiperiodic and minimal shifts of finite type.

[BibT_eX]

[DOI]

CoRR, 2018

An Operational Characterization of Mutual Information in Algorithmic Information Theory.

[BibT_eX]

[DOI]

Marius Zimand

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithmic Measures of Information for Tuples of Words and for Patterns in Multidimensional Shifts of Finite Type.

[BibT_eX]

[DOI]

, 2018

2017

On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.

[BibT_eX]

[DOI]

Dmitry Itsykson

Alexander Knop

Dmitry Sokolov

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

On the Expressive Power of Quasiperiodic SFT.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

Coding in the fork network in the framework of Kolmogorov complexity.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Topological Arguments for Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Conditional Information Inequalities and Combinatorial Applications.

[BibT_eX]

[DOI]

Nikolay K. Vereshchagin

CoRR, 2015

Quasiperiodicity and Non-computability in Tilings.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem.

[BibT_eX]

[DOI]

Daniyar Chumbalov

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

The axiomatic power of Kolmogorov complexity.

[BibT_eX]

[DOI]

Laurent Bienvenu

Antoine Taveneaux

Stijn Vermeeren

Ann. Pure Appl. Log., 2014

2013

Conditional Information Inequalities for Entropic and Almost Entropic Points.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2013

2012

Fixed-point tile sets and their applications.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

Conditional and unconditional information inequalities: an algebraic example

[BibT_eX]

[DOI]

CoRR, 2012

On the non-robustness of essentially conditional information inequalities.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011

Constraint information inequalities revisited

[BibT_eX]

[DOI]

CoRR, 2011

On essentially conditional information inequalities.

[BibT_eX]

[DOI]

Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Stability of properties of Kolmogorov complexity under relativization.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2010

1D Effectively Closed Subshifts and 2D Tilings.

[BibT_eX]

[DOI]

Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

Fixed Point Argument and Tilings without Long Range Order.

[BibT_eX]

[DOI]

Proceedings of the 7th Workshop on Fixed Points in Computer Science, 2010

Effective Closed Subshifts in 1D Can Be Implemented in 2D.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation, 2010

2009

Fixed Point Theorem and Aperiodic Tilings.

[BibT_eX]

Bull. EATCS, 2009

High Complexity Tilings with Sparse Errors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Variations on Muchnik's Conditional Complexity Theorem.

[BibT_eX]

[DOI]

Daniil Musatov

Proceedings of the Computer Science, 2009

2008

A Random Oracle Does Not Help Extract the Mutual Information.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Sparse sets.

[BibT_eX]

Laurent Bienvenu

Proceedings of the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008), 2008

Fixed Point and Aperiodic Tilings.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

2006

Reliable Computations Based on Locally Decodable Codes.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

2005

Resource bounded symmetry of information revisited.

[BibT_eX]

[DOI]

Troy Lee

Theor. Comput. Sci., 2005

2004

On Polynomially Time Bounded Symmetry of Information.

[BibT_eX]

[DOI]

Troy Lee

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

A Criterion for Extractability of Mutual Information for a Triple of Strings.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2003

Extracting the Mutual Information for a Triple of Binary Strings.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".

[BibT_eX]

[DOI]

Alexey V. Chernov

Theor. Comput. Sci., 2002

A new class of non-Shannon-type inequalities for entropies.

[BibT_eX]

[DOI]

Konstantin Makarychev

Yury Makarychev

Commun. Inf. Syst., 2002

2000

Inequalities for Shannon Entropy and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

J. Comput. Syst. Sci., 2000

Combinatorial Interpretation of Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1997

Inequalities for Shannon entropies and Kolmogorov complexities.

[BibT_eX]

[DOI]

Daniel Hammer