Selected papers by Andrei Romashchenko

  1. D.Chumbalov and A.Romashchenko. On the Combinatorial Version of the Slepian-Wolf Problem. IEEE Transactions on Information Theory. Volume 64, Issue 9, 2018, pp. 6054-6069. arXiv:1511.02899 Preliminary version: Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem, In Proc. MFCS 2015, Part 2, pp. 235-247.
  2. A.Romashchenko and M.Zimand. An operational characterization of mutual information in algorithmic information theory. Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Prague, Czech Republic, July 9-13, 2018. (LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, pp. 95:1-95:14). Extended version: arXiv:1710.05984
  3. J.Destombes and A.Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. (2018). arXiv:1805.03929
  4. T.Kaced, A.Romashchenko, and N.Vereshchagin. A Conditional Information Inequality and Its Combinatorial Applications. IEEE Transactions on Information Theory. Volume 64, Issue 5, 2018, pp. 3610-3615. arXiv:1501.04867
  5. B.Durand and A.Romashchenko. The Expressiveness of Quasiperiodic and Minimal Shifts of Finite Type. (2018) arXiv:1802.01461
  6. B.Durand and A.Romashchenko. On the Expressive Power of Quasiperiodic SFTs. Proc. 42th International Symposium in Mathematical Foundations of Computer Science (MFCS). Aalborg, Denmark, August 21-25, 2017. (LIPIcs 83, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017, pp. 5:1-5:14). Extended version: arXiv:1705.01876
  7. A.Romashchenko. Coding in the fork network in the framework of Kolmogorov complexity. (2016) download: arXiv:1602.02648
  8. B.Durand, A.Romashchenko. Quasiperiodicity and Non-computability in Tilings. Proc. 40th International Symposium in Mathematical Foundations of Computer Science (MFCS), Part 1. Milan, Italy, August 24-28, 2015. (Lecture Notes in Computer Science 9234, Springer, 2015, pp. 218-230). download: arXiv:1504.06130
  9. A.Shen, A.Romashchenko. Topological arguments for Kolmogorov complexity. Theory of Computing Systems. 56(3), 2015, pp. 513-526. (Preliminary version: Proc. 18th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), 2012, pp. 127-132.) Download: arXiv:1206.4927
  10. A.Romashchenko. Pseudo-random graphs and bit probe schemes with one-sided error. Theory of Computing Systems. 55(2), 2014, pp. 313-329. (Preliminary version: Proc. 6th International Computer Science Symposium in Russia (CSR), 2011.) download: arXiv:1102.5538, slides: pdf
  11. T.Kaced, A.Romashchenko. Conditional Information Inequalities for Entropic and Almost Entropic Points. IEEE Transactions on Information Theory. Volume 59, Issue 11, 2013, pp. 7149-7167. download:  arXiv:1207.5742
  12. B.Durand, A.Romashchenko, A.Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences. Volume 78, Issue 3, May 2012, pp. 731-764. download: arXiv:0910.2415
  13. T.Kaced, A.Romashchenko. On essentially conditional information inequalities. IEEE International Symposium on Information Theory (ISIT). 2011. download: arXiv:1103.2545, slides: pdf
  14. D.Musatov, A.Romashchenko, A.Shen. Variations on Muchnik's Conditional Complexity Theorem Theory Comput. Syst. 49 (2). 2011, pp. 227-245 Preliminary version: Proc. 4th International Computer Science Symposium in Russia (CSR). Novosibirsk, Russia, August 18-23, 2009. pp. 250-262. download: arXiv:0904.3116
  15. B.Durand, A.Romashchenko, A.Shen. Effective Closed Subshifts in 1D Can Be Implemented in 2D. Fields of Logic and Computation 2010, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday. Lecture Notes in Computer Science 6300, 2010, pp. 208-226. download: arXiv:1003.3103
  16. An.Muchnik, A.Romashchenko. Stability of properties of Kolmogorov complexity under relativization. Problems of information transmission. vol. 46, no. 1, 2010. download: pdf russian version: pdf
  17. B.Durand, A.Romashchenko, A.Shen. High Complexity Tilings with Sparse Errors. Proc. of 36th International Colloquium on Automata, Languages and Programming (ICALP). Rhodes, Greece, July 5-12, 2009. pp. 403-414. download: pdf
  18. B.Durand, A.Romashchenko, A.Shen Fixed point theorem and aperiodic tilings. Bulletin of the EATCS (The Logic in Computer Science Column by Yuri Gurevich) no. 97 (2009) pp. 126--136. download: pdf
  19. An.Muchnik, A.Romashchenko. A Random Oracle Does Not Help Extract the Mutual Information. Proc. 33rd International Symposium in Mathematical Foundations of Computer Science (MFCS). Torun, Poland, August 25-29, 2008. (Lecture Notes in Computer Science 5162 Springer 2008 pp. 527-538). download: pdf
  20. B.Durand, A.Romashchenko, A.Shen Fixed point and aperiodic tilings. In Proc. 12th International Conf. Developments in Language Theory (DLT) 2008 Kyoto, Japan, September 16-19. pp. 276-288. download: arXiv:0802.2432
  21. L.Bienvenu, A.Romashchenko, A.Shen. Sparse sets. Proc. First Symposium on Cellular Automata `Journees Automates Cellulaires' (JAC 2008) Uzes, France, April 2008. pp. 18-28. download: pdf
  22. A.Romashchenko. Reliable Computations Based on Locally Decodable Codes. Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS). Marseille, France, February 2006, pp. 537-548. download: pdf
  23. А.Ромащенко. Сложностная интепретация задачи о вилочной сети. Information Processes (electronic journal ISSN 1819-5822) 5 (2005) No. 1, pp. 20--28. download: pdf
  24. T.Lee and A.Romashchenko. Resource Bounded Symmetry of Information Revisited. Theoretical Computer Science. 345 (2005) No. 2-3, pp. 386-405. download: pdf
  25. A.Romashchenko. Extracting the Mutual Information for a Triple of Binary Strings. Proc. 18th Annual IEEE Conference on Computational Complexity (2003). Aarhus, Denmark, July 2003, pp. 221-235. download: ps
  26. K.Makarychev, Yu.Makarychev, A.Romashchenko, N.Vereshchagin. A New Class of non-Shannon Type Inequalities for Entropies. Communications in Information and Systems. 2 (2002) No. 2, pp. 147-166. download: pdf
  27. A.Romashchenko, A.Shen, N.Vereshchagin. Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science. 271 (2002) pp. 111-123. download corrected version: pdf
  28. A.Chernov, An.A.Muchnik, A.Shen, A.Romashchenko, N.K.Vereshchagin. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theoretical Computer Science. 271 (2002) pp. 69-95. download: ps
  29. D.Hammer, A.Romashchenko, A.Shen, N.Vereshchagin. Inequalities for Shannon Entropy and Kolmogorov Complexity. Journal of Computer and System Sciences. 60 (2000) pp. 442-464. download: ps
  30. A.E.Romashchenko. Pairs of Words with Nonmaterializable Mutual Information. Problems of Information Transmission. 36 (2000) No. 1, pp. 1-18. Originally published in Russian: А.Е.Ромащенко. Пары слов с нематериализуемой взаимной информацией. Проблемы передачи информации. 36 (2000) No. 1, стр. 3-20. download the english version: pdf download the russion version: pdf
  31. PhD Thesis

  32. А.Ромащенко. Неравенства для колмогоровской сложности и общая информация. Кандидатская диссертация. Москва, МГУ. 2000. download: pdf

Last Modified: Tue Sep 4 11:10 CEST 2018