Edit Profile (opens in new tab) Romashchenko, Andrei Co-Author Distance Author ID: romashchenko.andrei Published as: Romashchenko, Andrei; Romashchenko, A. E.; Romashchenko, Andrey; Romashchenko, A. more...less Further Spellings: ромащенко Homepage: https://www.lirmm.fr/~romashchen/ External Links: MGP · ORCID · Wikidata · arXiv · Math-Net.Ru · dblp Videos: carmin.tv Documents Indexed: 41 Publications since 2000, including 2 Additional arXiv Preprints Co-Authors: 23 Co-Authors with 34 Joint Publications 350 Co-Co-Authors all top 5 Co-Authors 7 single-authored 13 Shen, Alexander 7 Durand, Bruno 5 Vereshchagin, Nikolay K. 4 Kaced, Tarik 3 Muchnik, Andrej A. 2 Chumbalov, Daniyar 2 Destombes, Julien 2 Itsykson, Dmitry M. 2 Knop, Alexander 2 Lee, Troy 2 Musatov, Daniil 2 Sokolev, Dmitry 2 Zimand, Marius 1 Bauwens, Bruno 1 Bienvenu, Laurent 1 Chernov, Alekseĭ Vyacheslav 1 Gacs, Peter 1 Gürpınar, Emirhan 1 Hammer, Daniel 1 Makarychev, Konstantin S. 1 Makarychev, Yury S. 1 Taveneaux, Antoine 1 Vermeeren, Stijn all top 5 Serials 4 Theoretical Computer Science 3 IEEE Transactions on Information Theory 3 Problems of Information Transmission 3 Journal of Computer and System Sciences 3 Theory of Computing Systems 1 Moscow University Mathematics Bulletin 1 The Journal of Symbolic Logic 1 Ergodic Theory and Dynamical Systems 1 Annals of Pure and Applied Logic 1 Journal of the ACM 1 Communications in Information and Systems 1 Computability all top 5 Fields 33 Computer science (68-XX) 14 Information and communication theory, circuits (94-XX) 7 Mathematical logic and foundations (03-XX) 6 Combinatorics (05-XX) 6 Dynamical systems and ergodic theory (37-XX) 3 Convex and discrete geometry (52-XX) 2 Probability theory and stochastic processes (60-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Statistics (62-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 27 Publications have been cited 180 times in 132 Documents Cited by ▼ Year ▼ Fixed-point tile sets and their applications. Zbl 1244.05049 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 33 2012 Inequalities for Shannon entropy and Kolmogorov complexity. Zbl 0988.94016 Hammer, Daniel; Romashchenko, Andrei; Shen, Alexander; Vereshchagin, Nikolai 25 2000 A new class of non-Shannon-type inequalities for entropies. Zbl 1094.94017 Makarychev, Konstantin; Makarychev, Yury; Romashchenko, Andrei; Vereshchagin, Nikolai 21 2002 Effective closed subshifts in 1D can be implemented in 2D. Zbl 1287.37012 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 16 2010 Fixed point and aperiodic tilings. Zbl 1161.68033 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 9 2008 Upper semi-lattice of binary strings with the relation “\(x\) is simple conditional to \(y\)”. Zbl 0992.68085 Chernov, Alexei; Muchnik, Andrej; Romashchenko, Andrei; Shen, Alexander; Vereshchagin, Nikolai 8 2002 Combinatorial interpretation of Kolmogorov complexity. Zbl 0992.68081 Romashchenko, A.; Shen, A.; Vereshchagin, N. 8 2002 Variations on Muchnik’s conditional complexity theorem. Zbl 1235.68089 Musatov, Daniil; Romashchenko, Andrei; Shen, Alexander 7 2011 Resource bounded symmetry of information revisited. Zbl 1081.68034 Lee, Troy; Romashchenko, Andrei 7 2005 On OBDD-based algorithms and proof systems that dynamically change order of variables. Zbl 1402.68097 Itsykson, Dmitry; Knop, Alexander; Romashchenko, Andrey; Sokolov, Dmitry 6 2017 Conditional information inequalities for entropic and almost entropic points. Zbl 1364.94241 Kaced, Tarik; Romashchenko, Andrei 5 2013 On the expressive power of quasiperiodic SFT. Zbl 1441.37021 Durand, Bruno; Romashchenko, Andrei 5 2017 Stability of properties of Kolmogorov complexity under relativization. Zbl 1214.68182 Muchnik, An. A.; Romashchenko, A. E. 4 2010 Pairs of words with nonmaterializable mutual information. Zbl 1025.94007 Romashchenko, A. E. 4 2000 An operational characterization of mutual information in algorithmic information theory. Zbl 1473.68100 Romashchenko, Andrei; Zimand, Marius 3 2019 The axiomatic power of Kolmogorov complexity. Zbl 1351.03032 Bienvenu, Laurent; Romashchenko, Andrei; Shen, Alexander; Taveneaux, Antoine; Vermeeren, Stijn 2 2014 Topological arguments for Kolmogorov complexity. Zbl 1331.68119 Romashchenko, Andrei; Shen, Alexander 2 2015 Quasiperiodicity and non-computability in tilings. Zbl 1465.68085 Durand, Bruno; Romashchenko, Andrei 2 2015 A criterion for extractability of mutual information for a triple of strings. Zbl 1077.94008 Romashchenko, A. E. 2 2003 A conditional information inequality and its combinatorial applications. Zbl 1395.94213 Kaced, Tarik; Romashchenko, Andrei; Vereshchagin, Nikolai 2 2018 Pseudo-random graphs and bit probe schemes with one-sided error. Zbl 1330.68123 Romashchenko, Andrei 2 2011 Clustering with respect to the information distance. Zbl 1537.68059 Romashchenko, Andrei 1 2022 Pseudo-random graphs and bit probe schemes with one-sided error. Zbl 1319.68066 Romashchenko, Andrei 1 2014 On polynomially time bounded symmetry of information. Zbl 1096.68074 Lee, Troy; Romashchenko, Andrei 1 2004 Reliable computations based on locally decodable codes. Zbl 1136.68344 Romashchenko, Andrei 1 2006 High complexity tilings with sparse errors. Zbl 1248.68266 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 1 2009 Variations on Muchnik’s conditional complexity theorem. Zbl 1248.68269 Musatov, Daniil; Romashchenko, Andrei; Shen, Alexander 1 2009 Clustering with respect to the information distance. Zbl 1537.68059 Romashchenko, Andrei 1 2022 An operational characterization of mutual information in algorithmic information theory. Zbl 1473.68100 Romashchenko, Andrei; Zimand, Marius 3 2019 A conditional information inequality and its combinatorial applications. Zbl 1395.94213 Kaced, Tarik; Romashchenko, Andrei; Vereshchagin, Nikolai 2 2018 On OBDD-based algorithms and proof systems that dynamically change order of variables. Zbl 1402.68097 Itsykson, Dmitry; Knop, Alexander; Romashchenko, Andrey; Sokolov, Dmitry 6 2017 On the expressive power of quasiperiodic SFT. Zbl 1441.37021 Durand, Bruno; Romashchenko, Andrei 5 2017 Topological arguments for Kolmogorov complexity. Zbl 1331.68119 Romashchenko, Andrei; Shen, Alexander 2 2015 Quasiperiodicity and non-computability in tilings. Zbl 1465.68085 Durand, Bruno; Romashchenko, Andrei 2 2015 The axiomatic power of Kolmogorov complexity. Zbl 1351.03032 Bienvenu, Laurent; Romashchenko, Andrei; Shen, Alexander; Taveneaux, Antoine; Vermeeren, Stijn 2 2014 Pseudo-random graphs and bit probe schemes with one-sided error. Zbl 1319.68066 Romashchenko, Andrei 1 2014 Conditional information inequalities for entropic and almost entropic points. Zbl 1364.94241 Kaced, Tarik; Romashchenko, Andrei 5 2013 Fixed-point tile sets and their applications. Zbl 1244.05049 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 33 2012 Variations on Muchnik’s conditional complexity theorem. Zbl 1235.68089 Musatov, Daniil; Romashchenko, Andrei; Shen, Alexander 7 2011 Pseudo-random graphs and bit probe schemes with one-sided error. Zbl 1330.68123 Romashchenko, Andrei 2 2011 Effective closed subshifts in 1D can be implemented in 2D. Zbl 1287.37012 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 16 2010 Stability of properties of Kolmogorov complexity under relativization. Zbl 1214.68182 Muchnik, An. A.; Romashchenko, A. E. 4 2010 High complexity tilings with sparse errors. Zbl 1248.68266 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 1 2009 Variations on Muchnik’s conditional complexity theorem. Zbl 1248.68269 Musatov, Daniil; Romashchenko, Andrei; Shen, Alexander 1 2009 Fixed point and aperiodic tilings. Zbl 1161.68033 Durand, Bruno; Romashchenko, Andrei; Shen, Alexander 9 2008 Reliable computations based on locally decodable codes. Zbl 1136.68344 Romashchenko, Andrei 1 2006 Resource bounded symmetry of information revisited. Zbl 1081.68034 Lee, Troy; Romashchenko, Andrei 7 2005 On polynomially time bounded symmetry of information. Zbl 1096.68074 Lee, Troy; Romashchenko, Andrei 1 2004 A criterion for extractability of mutual information for a triple of strings. Zbl 1077.94008 Romashchenko, A. E. 2 2003 A new class of non-Shannon-type inequalities for entropies. Zbl 1094.94017 Makarychev, Konstantin; Makarychev, Yury; Romashchenko, Andrei; Vereshchagin, Nikolai 21 2002 Upper semi-lattice of binary strings with the relation “\(x\) is simple conditional to \(y\)”. Zbl 0992.68085 Chernov, Alexei; Muchnik, Andrej; Romashchenko, Andrei; Shen, Alexander; Vereshchagin, Nikolai 8 2002 Combinatorial interpretation of Kolmogorov complexity. Zbl 0992.68081 Romashchenko, A.; Shen, A.; Vereshchagin, N. 8 2002 Inequalities for Shannon entropy and Kolmogorov complexity. Zbl 0988.94016 Hammer, Daniel; Romashchenko, Andrei; Shen, Alexander; Vereshchagin, Nikolai 25 2000 Pairs of words with nonmaterializable mutual information. Zbl 1025.94007 Romashchenko, A. E. 4 2000 all cited Publications top 5 cited Publications all top 5 Cited by 148 Authors 17 Romashchenko, Andrei 15 Shen, Alexander 10 Sablik, Mathieu 8 Jeandel, Emmanuel 8 Vereshchagin, Nikolay K. 7 Barbieri, Sebastián 7 Durand, Bruno 6 Itsykson, Dmitry M. 6 Vanier, Pascal 5 Musatov, Daniil 5 Zimand, Marius 4 Farràs, Oriol 4 Padró, Carles 3 Aubrun, Nathalie 3 Bauwens, Bruno 3 Boege, Tobias 3 Glinskih, Ludmila 3 Törmä, Ilkka A. 2 Csirmaz, László 2 Fernique, Thomas 2 Gacs, Peter 2 Gangloff, Silvère 2 Gayral, Léo 2 Hirahara, Shuichi 2 Kari, Jarkko 2 Khazaei, Shahram 2 Knop, Alexander 2 Milovanov, Alexey 2 Moutot, Etienne 2 Muchnik, Andrej A. 2 Nagarajan, Rajagopal 2 Nies, André Otfrid 2 Pavlov, Ronnie 2 Rogers, Caroline 2 Salo, Ville O. 2 Simpson, Stephen G. 2 Sokolev, Dmitry 2 Terwijn, Sebastiaan A. 1 Alon, Noga 1 Alrabiah, Omar 1 Austin, Tim D. 1 Bamiloshin, Michael 1 Ben-Efraim, Aner 1 Berthé, Valérie 1 Bissacot, Rodrigo 1 Bolt, Janneke H. 1 Boston, Nigel 1 Boyle, Mike 1 Buss, Samuel R. 1 Buzzi, Jérôme 1 Calude, Cristian S. 1 Case, Adam 1 Chakraborty, Diptarka 1 Chan, Terence H. 1 Chavez, Gordon V. 1 Chernov, Alekseĭ Vyacheslav 1 Chong, Edwin Kah Pin 1 Chumbalov, Daniyar 1 Coeurjolly, Jean-François 1 Colbeck, Roger 1 Collet, Pierre 1 Downey, Rodney Graham 1 Drouilhet, Rémy 1 Epstein, Samuel 1 Esnay, Solène J. 1 Fatès, Nazim A. 1 Gamard, Guilhem 1 Grandjean, Anaël 1 Greenberg, Noam 1 Gürpınar, Emirhan 1 Guruswami, Venkatesan 1 He, Temple 1 Hirschfeldt, Denis Roman 1 Hochman, Michael 1 Hubeny, Veronika E. 1 Ilango, Rahul 1 Ishkuvatov, Ruslan 1 Jafari, Amir Homayoun 1 Jenkinson, Oliver 1 Jørgensen, Palle E. T. 1 Kaboli, Reza 1 Kaced, Tarik 1 Kahle, Thomas 1 Kalugin, Pavel 1 Katz, André 1 Kenig, Batya 1 Kinser, Ryan 1 Kothari, Pravesh K. 1 Kretschmer, Andreas 1 Lafitte, Grégory 1 Lee, Troy 1 Li, Hua 1 Li, Ming 1 Lu, Zhenjian 1 Lutz, Jack H. 1 Makhlin, Anton 1 Manohar, Peter 1 Marcovici, Irène 1 Martí-Farré, Jaume 1 Martín, Sebastià ...and 48 more Authors all top 5 Cited in 55 Serials 10 Theoretical Computer Science 10 Theory of Computing Systems 6 Ergodic Theory and Dynamical Systems 3 Journal of Computer and System Sciences 3 Kybernetika 3 Computational Complexity 3 Discrete and Continuous Dynamical Systems 2 Problems of Information Transmission 2 Proceedings of the American Mathematical Society 2 Journal of Cryptology 2 Entropy 2 International Journal of Quantum Information 2 Computability 1 Discrete Applied Mathematics 1 Discrete Mathematics 1 International Journal of General Systems 1 Israel Journal of Mathematics 1 Journal d’Analyse Mathématique 1 Moscow University Mathematics Bulletin 1 Scandinavian Journal of Statistics 1 Studia Mathematica 1 Advances in Mathematics 1 Applied Mathematics and Computation 1 Journal of Combinatorial Theory. Series A 1 The Journal of Symbolic Logic 1 Notre Dame Journal of Formal Logic 1 Tôhoku Mathematical Journal. Second Series 1 Transactions of the American Mathematical Society 1 European Journal of Combinatorics 1 Journal of Time Series Analysis 1 Acta Applicandae Mathematicae 1 Probability Theory and Related Fields 1 Discrete & Computational Geometry 1 SIAM Journal on Discrete Mathematics 1 International Journal of Foundations of Computer Science 1 Designs, Codes and Cryptography 1 Linear Algebra and its Applications 1 Experimental Mathematics 1 Computational Optimization and Applications 1 The Bulletin of Symbolic Logic 1 Electronic Journal of Probability 1 Nonlinear Dynamics 1 Journal of Mathematical Logic 1 Fundamenta Informaticae 1 Journal of High Energy Physics 1 Brazilian Journal of Probability and Statistics 1 Analysis and Applications (Singapore) 1 Journal of Mathematical Cryptology 1 Journal of Modern Dynamics 1 Logical Methods in Computer Science 1 Acta Crystallographica. Section A 1 ACM Transactions on Computation Theory 1 Proceedings of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences 1 Discrete Analysis 1 Advances in Combinatorics all top 5 Cited in 28 Fields 65 Computer science (68-XX) 40 Dynamical systems and ergodic theory (37-XX) 30 Information and communication theory, circuits (94-XX) 28 Mathematical logic and foundations (03-XX) 19 Combinatorics (05-XX) 11 Convex and discrete geometry (52-XX) 8 Statistics (62-XX) 5 Group theory and generalizations (20-XX) 5 Probability theory and stochastic processes (60-XX) 4 Operations research, mathematical programming (90-XX) 3 Quantum theory (81-XX) 2 Order, lattices, ordered algebraic structures (06-XX) 2 Measure and integration (28-XX) 2 Statistical mechanics, structure of matter (82-XX) 2 Biology and other natural sciences (92-XX) 1 General and overarching topics; collections (00-XX) 1 Number theory (11-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Topological groups, Lie groups (22-XX) 1 Potential theory (31-XX) 1 Difference and functional equations (39-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.