Andrei Romashchenko

89 papers A* 1A 8B 9C 1Misc 2Journal 59Unranked 8
YearRankTypeTitle / Venue / Authors
2026 J jnl
Algebraic barriers to halving algorithmic information quantities in correlated strings.
Inf. Comput.
Andrei Romashchenko
2026 J jnl
Spectral Conditions for the Ingleton Inequality.
CoRR
Rostislav Matveev, Andrei Romashchenko
2025 B conf
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings.
MFCS
Andrei Romashchenko
2025 J jnl
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings.
CoRR
Andrei Romashchenko
2025 J jnl
Structural Properties of Entropic Vectors and Stability of the Ingleton Inequality.
CoRR
Rostislav Matveev, Andrei Romashchenko
2024 B conf
Common Information in Well-Mixing Graphs and Applications to Information-Theoretic Cryptography.
ITW
Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov
2024 J jnl
Common information in well-mixing graphs and applications to information-theoretic cryptography.
CoRR
Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov
2024 J jnl
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory.
ACM Trans. Comput. Theory
Emirhan Gürpinar, Andrei Romashchenko
2024 A conf
Spectral Approach to the Communication Complexity of Multi-Party Key Agreement.
STACS
Geoffroy Caillat-Grenier, Andrei Romashchenko
2023 J jnl
Spectral approach to the communication complexity of multi-party key agreement.
CoRR
Geoffroy Caillat-Grenier, Andrei Romashchenko
2022 J jnl
27 Open Problems in Kolmogorov Complexity.
CoRR
Andrei Romashchenko, Alexander Shen, Marius Zimand
2022 J jnl
Clustering with respect to the information distance.
Theor. Comput. Sci.
Andrei Romashchenko
2022 J jnl
Inequalities for space-bounded Kolmogorov complexity.
Comput.
Bruno Bauwens, Péter Gács, Andrei Romashchenko, Alexander Shen
2022 J jnl
Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts.
J. Comput. Syst. Sci.
Julien Destombes, Andrei Romashchenko
2021 J jnl
27 Open Problems in Kolmogorov Complexity.
SIGACT News
Andrei Romashchenko, Alexander Shen, Marius Zimand
2021 J jnl
Clustering with Respect to the Information Distance.
CoRR
Andrei Romashchenko
2020 B conf
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory.
MFCS
Emirhan Gürpinar, Andrei Romashchenko
2020 J jnl
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory.
CoRR
Emirhan Gürpinar, Andrei Romashchenko
2020 J jnl
Inequalities for space-bounded Kolmogorov complexity.
CoRR
Péter Gács, Andrei Romashchenko, Alexander Shen
2020 J jnl
On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables.
J. Symb. Log.
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2019 J jnl
An Operational Characterization of Mutual Information in Algorithmic Information Theory.
J. ACM
Andrei Romashchenko, Marius Zimand
2019 B conf
How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma.
ISIT
Emirhan Gürpinar, Andrei Romashchenko
2019 J jnl
How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma.
CoRR
Emirhan Gürpinar, Andrei Romashchenko
2019 J jnl
On OBDD-based algorithms and proof systems that dynamically change order of variables.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2019 J jnl
On a conditional inequality in Kolmogorov complexity and its applications in communication complexity.
CoRR
Andrei Romashchenko, Marius Zimand
2019 A conf
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts.
STACS
Julien Destombes, Andrei Romashchenko
2018 J jnl
A Conditional Information Inequality and Its Combinatorial Applications.
IEEE Trans. Inf. Theory
Tarik Kaced, Andrei Romashchenko, Nikolai K. Vereshchagin
2018 — book
Algorithmic Measures of Information for Tuples of Words and for Patterns in Multidimensional Shifts of Finite Type.
Andrei Romashchenko
2018 A* conf
An Operational Characterization of Mutual Information in Algorithmic Information Theory.
ICALP
Andrei Romashchenko, Marius Zimand
2018 J jnl
An operational characterization of mutual information in algorithmic information theory.
Electron. Colloquium Comput. Complex.
Andrei Romashchenko, Marius Zimand
2018 J jnl
On the Combinatorial Version of the Slepian-Wolf Problem.
IEEE Trans. Inf. Theory
Daniyar Chumbalov, Andrei Romashchenko
2018 J jnl
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts.
CoRR
Julien Destombes, Andrei Romashchenko
2018 J jnl
The expressiveness of quasiperiodic and minimal shifts of finite type.
CoRR
Bruno Durand, Andrei Romashchenko
2017 J jnl
An operational characterization of mutual information in algorithmic information theory.
CoRR
Andrei Romashchenko, Marius Zimand
2017 A conf
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables.
STACS
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov
2017 B conf
On the Expressive Power of Quasiperiodic SFT.
MFCS
Bruno Durand, Andrei Romashchenko
2017 J jnl
On the expressive power of quasiperiodic SFT.
CoRR
Bruno Durand, Andrei Romashchenko
2016 J jnl
Coding in the fork network in the framework of Kolmogorov complexity.
CoRR
Andrei Romashchenko
2015 J jnl
Conditional Information Inequalities and Combinatorial Applications.
CoRR
Tarik Kaced, Andrei Romashchenko, Nikolay K. Vereshchagin
2015 J jnl
On the Combinatorial Version of the Slepian-Wolf Problem.
CoRR
Daniyar Chumbalov, Andrei Romashchenko
2015 — conf
Quasiperiodicity and Non-computability in Tilings.
MFCS (1)
Bruno Durand, Andrei Romashchenko
2015 J jnl
Quasiperiodicity and non-computability in tilings.
CoRR
Bruno Durand, Andrei Romashchenko
2015 — conf
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem.
MFCS (2)
Daniyar Chumbalov, Andrei Romashchenko
2015 J jnl
Topological Arguments for Kolmogorov Complexity.
Theory Comput. Syst.
Andrei Romashchenko, Alexander Shen
2014 J jnl
Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error.
Theory Comput. Syst.
Andrei Romashchenko
2014 J jnl
The axiomatic power of Kolmogorov complexity.
Ann. Pure Appl. Log.
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
2013 J jnl
Conditional Information Inequalities for Entropic and Almost Entropic Points.
IEEE Trans. Inf. Theory
Tarik Kaced, Andrei Romashchenko
2013 J jnl
The axiomatic power of Kolmogorov complexity
CoRR
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
2012 J jnl
Conditional Information Inequalities for Entropic and Almost Entropic Points
CoRR
Tarik Kaced, Andrei Romashchenko
2012 J jnl
Conditional and unconditional information inequalities: an algebraic example
CoRR
Tarik Kaced, Andrei Romashchenko
2012 J jnl
Fixed-point tile sets and their applications.
J. Comput. Syst. Sci.
Bruno Durand, Andrei Romashchenko, Alexander Shen
2012 J jnl
On the Non-robustness of Essentially Conditional Information Inequalities
CoRR
Tarik Kaced, Andrei Romashchenko
2012 B conf
On the non-robustness of essentially conditional information inequalities.
ITW
Tarik Kaced, Andrei Romashchenko
2012 — conf
Topological arguments for Kolmogorov complexity
AUTOMATA & JAC
Alexander Shen, Andrei Romashchenko
2011 J jnl
Constraint information inequalities revisited
CoRR
Tarik Kaced, Andrei Romashchenko
2011 B conf
On essentially conditional information inequalities.
ISIT
Tarik Kaced, Andrei Romashchenko
2011 Misc conf
Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error.
CSR
Andrei Romashchenko
2011 J jnl
Pseudo-random graphs and bit probe schemes with one-sided error
CoRR
Andrei Romashchenko
2011 J jnl
Variations on Muchnik's Conditional Complexity Theorem.
Theory Comput. Syst.
Daniil Musatov, Andrei Romashchenko, Alexander Shen
2010 J jnl
1D Effectively Closed Subshifts and 2D Tilings
CoRR
Bruno Durand, Alexander Shen, Andrei Romashchenko
2010 — conf
1D Effectively Closed Subshifts and 2D Tilings.
JAC
Bruno Durand, Andrei Romashchenko, Alexander Shen
2010 — conf
Effective Closed Subshifts in 1D Can Be Implemented in 2D.
Fields of Logic and Computation
Bruno Durand, Andrei Romashchenko, Alexander Shen
2010 J jnl
Effective closed subshifts in 1D can be implemented in 2D
CoRR
Bruno Durand, Andrei Romashchenko, Alexander Shen
2010 — conf
Fixed Point Argument and Tilings without Long Range Order.
FICS
Andrei Romashchenko
2010 J jnl
Fixed point theorem and aperiodic tilings
CoRR
Bruno Durand, Andrei Romashchenko, Alexander Shen
2009 J jnl
Fixed Point Theorem and Aperiodic Tilings.
Bull. EATCS
Bruno Durand, Andrei Romashchenko, Alexander Shen
2009 J jnl
Fixed-point tile sets and their applications
CoRR
Bruno Durand, Andrei Romashchenko, Alexander Shen
2009 — conf
High Complexity Tilings with Sparse Errors.
ICALP (1)
Bruno Durand, Andrei Romashchenko, Alexander Shen
2009 J jnl
Variations on Muchnik's Conditional Complexity Theorem
CoRR
Daniil Musatov, Andrei Romashchenko, Alexander Shen
2009 Misc conf
Variations on Muchnik's Conditional Complexity Theorem.
CSR
Daniil Musatov, Andrei Romashchenko, Alexander Shen
2008 B conf
A Random Oracle Does Not Help Extract the Mutual Information.
MFCS
Andrei A. Muchnik, Andrei Romashchenko
2008 J jnl
Fixed Point and Aperiodic Tilings
CoRR
Bruno Durand, Andrei Romashchenko, Alexander Shen
2008 C conf
Fixed Point and Aperiodic Tilings.
Developments in Language Theory
Bruno Durand, Andrei Romashchenko, Alexander Shen
2008 J jnl
Fixed Point and Aperiodic Tilings.
Electron. Colloquium Comput. Complex.
Bruno Durand, Alexander Shen, Andrei Romashchenko
2008 — conf
Sparse sets.
JAC
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen
2006 A conf
Reliable Computations Based on Locally Decodable Codes.
STACS
Andrei Romashchenko
2005 J jnl
Resource bounded symmetry of information revisited.
Theor. Comput. Sci.
Troy Lee, Andrei Romashchenko
2004 J jnl
On Polynomially Time Bounded Symmetry of Information
Electron. Colloquium Comput. Complex.
Troy Lee, Andrei Romashchenko
2004 B conf
On Polynomially Time Bounded Symmetry of Information.
MFCS
Troy Lee, Andrei Romashchenko
2003 J jnl
A Criterion for Extractability of Mutual Information for a Triple of Strings.
Probl. Inf. Transm.
Andrei Romashchenko
2003 A conf
Extracting the Mutual Information for a Triple of Binary Strings.
CCC
Andrei Romashchenko
2002 J jnl
A new class of non-Shannon-type inequalities for entropies.
Commun. Inf. Syst.
Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai K. Vereshchagin
2002 J jnl
Combinatorial interpretation of Kolmogorov complexity.
Theor. Comput. Sci.
Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2002 J jnl
Upper semi-lattice of binary strings with the relation "x is simple conditional to y".
Theor. Comput. Sci.
Alexey V. Chernov, Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000 J jnl
Combinatorial Interpretation of Kolmogorov Complexity
Electron. Colloquium Comput. Complex.
Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000 A conf
Combinatorial Interpretation of Kolmogorov Complexity.
CCC
Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000 J jnl
Inequalities for Shannon Entropy and Kolmogorov Complexity.
J. Comput. Syst. Sci.
Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1999 A conf
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".
CCC
Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1997 A conf
Inequalities for Shannon entropies and Kolmogorov complexities.
CCC
Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin