Some papers by Andrei Romashchenko

  1. 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
  2. B.Durand, A.Romashchenko, A.Shen. Fixed-point tile sets and their applications. 2009, arXiv:0910.2415 (submitted). download : ps,pdf
  3. 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
  4. 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
  5. D.Musatov, A.Romashchenko, A.Shen. Variations on Muchnik's Conditional Complexity Theorem Proc. 4th International Computer Science Symposium in Russia (CSR). Novosibirsk, Russia, August 18-23, 2009. pp. 250-262 download : ps,pdf
  6. 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
  7. B.Durand, A.Romashchenko, A.Shen Fixed pointexit and aperiodic tilings. In Proc. 12th International Conf. Developments in Language Theory (DLT) 2008 Kyoto, Japan, September 16-19. pp. 276-288. download: ps,pdf
  8. L.Beinvenu, 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
  9. 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
  10. А.Ромащенко. Сложностная интепретация задачи о вилочной сети. Information Processes (electronic journal ISSN 1819-5822) 5 (2005) No. 1, pp. 20--28. download: pdf
  11. T.Lee and A.Romashchenko. Resource Bounded Symmetry of Information Revisited. Theoretical Computer Science. 345 (2005) No. 2-3, pp. 386-405. download: pdf
  12. 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 (preliminary version): ps
  13. 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
  14. A.Romashchenko, A.Shen, N.Vereshchagin. Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science. 271 (2002) pp. 111-123. download corrected version: pdf
  15. 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
  16. 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
  17. 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 russion version): ps

    18. PhD Thesis

  18. А.Ромащенко. Неравенства для колмогоровской сложности и общая информация. Кандидатская диссертация. Москва, МГУ. 2000. download : ps
Last Modified: Sun Mar 28 11:10 MSC 2010