Some papers by Andrei Romashchenko

  1. T.Kaced, A.Romashchenko. On essentially conditional information inequalities. IEEE International Symposium on Information Theory (ISIT). 2011. download: pdf, slides: pdf
  2. A.Romashchenko. Pseudo-random graphs and bit probe schemes with one-sided error. Proc. 6th International Computer Science Symposium in Russia (CSR). 2011. download: pdf, slides: pdf
  3. 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: pdf
  4. 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
  5. B.Durand, A.Romashchenko, A.Shen. Fixed-point tile sets and their applications. 2009, arXiv:0910.2415 (submitted). download: ps,pdf
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. А.Ромащенко. Сложностная интепретация задачи о вилочной сети. Information Processes (electronic journal ISSN 1819-5822) 5 (2005) No. 1, pp. 20--28. download: pdf
  14. T.Lee and A.Romashchenko. Resource Bounded Symmetry of Information Revisited. Theoretical Computer Science. 345 (2005) No. 2-3, pp. 386-405. download: pdf
  15. 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
  16. 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
  17. A.Romashchenko, A.Shen, N.Vereshchagin. Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science. 271 (2002) pp. 111-123. download corrected version: pdf
  18. 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
  19. 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
  20. 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): pdf

    21. PhD Thesis

  21. А.Ромащенко. Неравенства для колмогоровской сложности и общая информация. Кандидатская диссертация. Москва, МГУ. 2000. download: ps
Last Modified: Fri Aug 05 00:10 MSC 2011