Selected publications of Andrei Romashchenko:

  1. G. Caillat-Grenier, A. Romashchenko, R. Zyavgarov. Common information in well-mixing graphs and applications to information-theoretic cryptography. In Proc. IEEE Information Theory Workshop (ITW) 2024, pp. 181-186. Extended version: arXiv:2405.05831
  2. E. Gürpınar and A. Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. ACM Transactions on Computation Theory. Volume 16, Issue 3, 2024, Article No. 13, pp. 1-37. (Conference version: In Proc. MFCS 2020.) arXiv:2004.13411
  3. G. Caillat-Grenier and A. Romashchenko. Spectral approach to the communication complexity of multi-party key agreement. In Proc. 41st International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Volume 289, 2024, pp. 22:1-22:19. arXiv:2305.01355
  4. B. Bauwens, P. Gacs, A. Romashchenko, and A. Shen. Inequalities for space-bounded Kolmogorov complexity. Computability, Volume 11, Issue 3-4, 2022, pp. 165-185. arXiv:2010.10221
  5. A. Romashchenko. Clustering with Respect to the Information Distance. Theoretical Computer Science, Volume 929, 2022, pp. 164-172. arXiv:2110.01346
  6. J. Destombes and A. Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. Journal of Computer and System Sciences Volume 128, Issue 2, 2022, pp. 107-134. Conference version: in Proc. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pp. 23:1-23:17. arXiv:1805.03929
  7. A. Romashchenko, A. Shen, M. Zimand. 27 Open Problems in Kolmogorov Complexity. ACM SIGACT News Volume 52, Issue 4, 2021, pp. 31-54. arXiv:2203.15109
  8. B. Durand and A. Romashchenko. The Expressiveness of Quasiperiodic and Minimal Shifts of Finite Type. Ergodic Theory and Dynamical Systems. Volume 44, Issue 4, 2021, pp. 1086-1138. (Preliminary version: Proc. MFCS 2015 and MFCS 2017.) arXiv:1802.01461
  9. D. Itsykson, A. Knop, A. Romashchenko, D. Sokolov. On OBDD-based algorithms and proof systems that dynamically change order of variables. Journal of Symbolic Logic Volume 85, Issue 2, 2020, pp. 632-670. Electronic Colloquium on Computational Complexity (ECCC): TR19-001, 30 pp. Conference version: in Proc. STACS 2017, pp. 43:1-43:14.
  10. A. Romashchenko and M. Zimand. An operational characterization of mutual information in algorithmic information theory. Journal of the ACM. Volume 66, Issue 5, September 2019, article no. 38. Preliminary version: in Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 95:1-95:14. arXiv: arXiv:1710.05984
  11. E. Gürpınar and A. Romashchenko. How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma. Proc. IEEE International Symposium on Information Theory (ISIT). Paris, France, July 8-12, 2019. pp. 1377-1381. arXiv:1901.07476
  12. A. Romashchenko. Algorithmic Measures of Information for Tuples of Words and for Patterns in Multidimensional Shifts of Finite Type. HDR, University of Montpellier (2018). hal-lirmm.ccsD. Cnrs.fr/tel-01963881
  13. 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.
  14. 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
  15. A. Romashchenko. Coding in the fork network in the framework of Kolmogorov complexity. (2016) arXiv:1602.02648
  16. 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.) arXiv:1206.4927
  17. 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.) arXiv:1102.5538, slides: pdf
  18. 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. arXiv:1207.5742
  19. 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. arXiv:0910.2415
  20. 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. arXiv:0904.3116
  21. 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. arXiv:1003.3103
  22. An. Muchnik, A. Romashchenko. Stability of properties of Kolmogorov complexity under relativization. Problems of information transmission. vol. 46, no. 1, 2010. Download: English version, Russian version. Preliminary version: A Random Oracle Does Not Help Extract the Mutual Information, in Proc. 33rd MFCS (2008), pp. 527-538.
  23. 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
  24. 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
  25. 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
  26. T. Lee and A. Romashchenko. Resource Bounded Symmetry of Information Revisited. Theoretical Computer Science. 345 (2005) No. 2-3, pp. 386-405. download: pdf
  27. 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
  28. A. Romashchenko, A. Shen, N. Vereshchagin. Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science. 271 (2002) pp. 111-123. download corrected version: pdf
  29. 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
  30. 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
  31. A. E. Romashchenko. Pairs of Words with Nonmaterializable Mutual Information. Problems of Information Transmission. 36 (2000) No. 1, pp. 1-18. download the english version: pdf
Last update: Jan 01, 2025