Andrei E. Romashchenko

According to our database, Andrei E. Romashchenko authored at least 52 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

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

Emirhan Gürpinar, Andrei E. Romashchenko

ACM Trans. Comput. Theory, September, 2024

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

Geoffroy Caillat-Grenier, Andrei E. Romashchenko

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.

Geoffroy Caillat-Grenier, Andrei E. Romashchenko, Rustam Zyavgarov

Proceedings of the IEEE Information Theory Workshop, 2024

2022

Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301).

Phokion G. Kolaitis, Andrei E. Romashchenko, Milan Studený, Dan Suciu, Tobias Boege

Dagstuhl Reports, July, 2022

Clustering with respect to the information distance.

Andrei E. Romashchenko

Theor. Comput. Sci., 2022

Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts.

Julien Destombes, Andrei E. Romashchenko

J. Comput. Syst. Sci., 2022

Inequalities for space-bounded Kolmogorov complexity.

Bruno Bauwens, Péter Gács, Andrei E. Romashchenko, Alexander Shen

Comput., 2022

2021

27 Open Problems in Kolmogorov Complexity.

Andrei E. Romashchenko, Alexander Shen, Marius Zimand

SIGACT News, 2021

2020

On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.

Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov

J. Symb. Log., 2020

Inequalities for space-bounded Kolmogorov complexity.

Péter Gács, Andrei E. Romashchenko, Alexander Shen

CoRR, 2020

2019

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

Andrei E. Romashchenko, Marius Zimand

CoRR, 2019

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

Emirhan Gürpinar, Andrei E. Romashchenko

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

A Conditional Information Inequality and Its Combinatorial Applications.

Tarik Kaced, Andrei E. Romashchenko, Nikolai K. Vereshchagin

IEEE Trans. Inf. Theory, 2018

On the Combinatorial Version of the Slepian-Wolf Problem.

Daniyar Chumbalov, Andrei E. Romashchenko

IEEE Trans. Inf. Theory, 2018

An operational characterization of mutual information in algorithmic information theory.

Andrei E. Romashchenko, Marius Zimand

Electron. Colloquium Comput. Complex., 2018

The expressiveness of quasiperiodic and minimal shifts of finite type.

Bruno Durand, Andrei E. Romashchenko

CoRR, 2018

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

Andrei E. Romashchenko

, 2018

2017

On the Expressive Power of Quasiperiodic SFT.

Bruno Durand, Andrei E. Romashchenko

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.

Andrei E. Romashchenko

CoRR, 2016

2015

Conditional Information Inequalities and Combinatorial Applications.

Tarik Kaced, Andrei E. Romashchenko, Nikolay K. Vereshchagin

CoRR, 2015

Quasiperiodicity and Non-computability in Tilings.

Bruno Durand, Andrei E. Romashchenko

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem.

Daniyar Chumbalov, Andrei E. Romashchenko

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

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

Andrei E. Romashchenko

Theory Comput. Syst., 2014

The axiomatic power of Kolmogorov complexity.

Laurent Bienvenu, Andrei E. Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren

Ann. Pure Appl. Log., 2014

2013

Conditional Information Inequalities for Entropic and Almost Entropic Points.

Tarik Kaced, Andrei E. Romashchenko

IEEE Trans. Inf. Theory, 2013

2012

Fixed-point tile sets and their applications.

Bruno Durand, Andrei E. Romashchenko, Alexander Shen

J. Comput. Syst. Sci., 2012

Topological arguments for Kolmogorov complexity

Alexander Shen, Andrei E. Romashchenko

Proceedings of the Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, 2012

Conditional and unconditional information inequalities: an algebraic example

Tarik Kaced, Andrei E. Romashchenko

CoRR, 2012

On the non-robustness of essentially conditional information inequalities.

Tarik Kaced, Andrei E. Romashchenko

Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011

Variations on Muchnik's Conditional Complexity Theorem.

Daniil Musatov, Andrei E. Romashchenko, Alexander Shen

Theory Comput. Syst., 2011

Constraint information inequalities revisited

Tarik Kaced, Andrei E. Romashchenko

CoRR, 2011

On essentially conditional information inequalities.

Tarik Kaced, Andrei E. Romashchenko

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

2010

Stability of properties of Kolmogorov complexity under relativization.

Andrei A. Muchnik, Andrei E. Romashchenko

Probl. Inf. Transm., 2010

1D Effectively Closed Subshifts and 2D Tilings.

Bruno Durand, Andrei E. Romashchenko, Alexander Shen

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

Fixed Point Argument and Tilings without Long Range Order.

Andrei E. Romashchenko

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

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

Bruno Durand, Andrei E. Romashchenko, Alexander Shen

Proceedings of the Fields of Logic and Computation, 2010

2009

Fixed Point Theorem and Aperiodic Tilings.

Bruno Durand, Andrei E. Romashchenko, Alexander Shen

Bull. EATCS, 2009

High Complexity Tilings with Sparse Errors.

Bruno Durand, Andrei E. Romashchenko, Alexander Shen

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

2008

Fixed Point and Aperiodic Tilings.

Bruno Durand, Alexander Shen, Andrei E. Romashchenko

Electron. Colloquium Comput. Complex., 2008

A Random Oracle Does Not Help Extract the Mutual Information.

Andrei A. Muchnik, Andrei E. Romashchenko

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Sparse sets.

Laurent Bienvenu, Andrei E. Romashchenko, Alexander Shen

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

2006

Reliable Computations Based on Locally Decodable Codes.

Andrei E. Romashchenko

Proceedings of the STACS 2006, 2006

2005

Resource bounded symmetry of information revisited.

Troy Lee, Andrei E. Romashchenko

Theor. Comput. Sci., 2005

2004

On Polynomially Time Bounded Symmetry of Information

Troy Lee, Andrei E. Romashchenko

Electron. Colloquium Comput. Complex., 2004

2003

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

Andrei E. Romashchenko

Probl. Inf. Transm., 2003

Extracting the Mutual Information for a Triple of Binary Strings.

Andrei E. Romashchenko

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

2002

Combinatorial interpretation of Kolmogorov complexity.

Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

Theor. Comput. Sci., 2002

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

Alexey V. Chernov, Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

Theor. Comput. Sci., 2002

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

Konstantin Makarychev, Yury Makarychev, Andrei E. Romashchenko, Nikolai K. Vereshchagin

Commun. Inf. Syst., 2002

2000

Inequalities for Shannon Entropy and Kolmogorov Complexity.

Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

J. Comput. Syst. Sci., 2000

1999

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

Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

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

1997

Inequalities for Shannon entropies and Kolmogorov complexities.

Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997