Andrei E. Romashchenko

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 35

Top Topics

Kolmogorov Complexity

Expressive Power

Algorithmic Information Theory

Top Venues

IEEE Trans. Inf. Theory

Publications

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