Skip to Main content
Number of documents

29

CV HAL : Andrei Romashchenko


See more detailes on my homepage


Journal articles11 documents

  • Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov. On Obdd-Based Algorithms and Proof Systems that Dynamically Change Order of Variables. The Journal of Symbolic Logic, Association for Symbolic Logic, In press, pp.1-41. ⟨10.1017/jsl.2019.53⟩. ⟨lirmm-02885744⟩
  • Bruno Durand, Andrei Romashchenko. The expressiveness of quasiperiodic and minimal shifts of finite type. Ergodic Theory and Dynamical Systems, Cambridge University Press (CUP), In press, ⟨10.1017/etds.2019.112⟩. ⟨hal-01702549⟩
  • Andrei Romashchenko, Marius Zimand. An Operational Characterization of Mutual Information in Algorithmic Information Theory. Journal of the ACM (JACM), Association for Computing Machinery, 2019, 66 (5), pp.1-42. ⟨10.1145/3356867⟩. ⟨lirmm-02297056⟩
  • Andrei Romashchenko, Tarik Kaced, Nikolai Vereshchagin. A Conditional Information Inequality and Its Combinatorial Applications. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩. ⟨lirmm-01793775⟩
  • Daniyar Chumbalov, Andrei Romashchenko. On the Combinatorial Version of the Slepian-Wolf Problem. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054 - 6069. ⟨10.1109/TIT.2018.2854589⟩. ⟨lirmm-01233020⟩
  • Andrei Romashchenko, Alexander Shen. Topological Arguments for Kolmogorov Complexity. Theory of Computing Systems, Springer Verlag, 2015, 56 (3), pp.513-526. ⟨10.1007/s00224-015-9606-8⟩. ⟨hal-01165095⟩
  • Andrei Romashchenko. Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error. Theory of Computing Systems, Springer Verlag, 2014, 55 (2), pp.313-329. ⟨10.1007/s00224-012-9425-0⟩. ⟨hal-01165099⟩
  • Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren. The axiomatic power of Kolmogorov complexity. Annals of Pure and Applied Logic, Elsevier Masson, 2014, 165 (9), pp.1380-1402. ⟨10.1016/j.apal.2014.04.009⟩. ⟨hal-01165098⟩
  • Tarik Kaced, Andrei Romashchenko. Conditional Information Inequalities for Entropic and Almost Entropic Points. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2013, 59 (11), pp.7149-7167. ⟨10.1109/TIT.2013.2274614⟩. ⟨lirmm-00848455⟩
  • Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, Elsevier, 2012, 78 (3), pp.731-764. ⟨10.1016/j.jcss.2011.11.001⟩. ⟨lirmm-00736079v3⟩
  • Daniil Musatov, Andrei Romashchenko, Alexander Shen. Variations on Muchnik's Conditional Complexity Theorem. Theory of Computing Systems, Springer Verlag, 2011, 9 (2), pp.227-245. ⟨lirmm-00736106⟩

Conference papers17 documents

  • Emirhan Gürpınar, Andrei Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. 45th International Symposium on Mathematical Foundations of Computer Science, Aug 2020, Prague, Czech Republic. ⟨lirmm-02558566⟩
  • Emirhan Gürpınar, Andrei Romashchenko. How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma. 2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019, Paris, France. pp.1377-1381, ⟨10.1109/ISIT.2019.8849309⟩. ⟨lirmm-01990325⟩
  • Andrei Romashchenko, Julien Destombes. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩. ⟨lirmm-01793810⟩
  • Andrei Romashchenko, Marius Zimand. An operational characterization of mutual information in algorithmic information theory. ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. pp.95:1-95:14, ⟨10.4230/LIPIcs.ICALP.2018.95⟩. ⟨lirmm-01618559⟩
  • Andrei Romashchenko, Bruno Durand. On the expressive power of quasiperiodic SFT. MFCS: Mathematical Foundations of Computer Science, Aug 2017, Aalborg, Denmark. pp.5:1-5:14, ⟨10.4230/LIPIcs.MFCS.2017.5⟩. ⟨lirmm-01623207⟩
  • Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov. On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩. ⟨lirmm-01487646⟩
  • Daniyar Chumbalov, Andrei Romashchenko. Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.235-247, ⟨10.1007/978-3-662-48054-0_20⟩. ⟨lirmm-01233012⟩
  • Bruno Durand, Andrei Romashchenko. Quasiperiodicity and non-computability in tilings. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.218-230, ⟨10.1007/978-3-662-48057-1_17⟩. ⟨lirmm-01165314⟩
  • Andrei Romashchenko, Alexander Shen. Topological arguments for Kolmogorov complexity. AUTOMATA, Sep 2012, La Marana, Furiani, France. pp.127-132. ⟨lirmm-00736127⟩
  • Tarik Kaced, Andrei Romashchenko. On the Non-robustness of Essentially Conditional Information Inequalities. ITW'12: Information Theory Workshop, Sep 2012, Switzerland. pp.1935-1939. ⟨lirmm-00736192⟩
  • Andrei Romashchenko. Pseudo-random graphs and bit probe schemes with one-sided error. CSR: Computer Science in Russia, Jun 2011, Saint Petersburg, Russia. pp.50-63, ⟨10.1007/978-3-642-20712-9_5⟩. ⟨lirmm-00736119⟩
  • Tarik Kaced, Andrei Romashchenko. On Essentially Conditional Information Inequalities. ISIT'11: International Symposium on Information Theory, Jul 2011, St. Petersburg, Russia. pp.1935-1939, ⟨10.1109/ISIT.2011.6033889⟩. ⟨lirmm-00736159⟩
  • Bruno Durand, Andrei Romashchenko, Alexander Shen. 1D Effectively Closed Subshifts and 2D Tilings. Journées Automates Cellulaires, Dec 2010, Turku, Finland. pp.2-7. ⟨hal-00541881⟩
  • Dale Miller, Arnaud Carayol, Panos Rondogiannis, Lars Birkedal, Marek Czarnecki, et al.. FICS 2010. 7th Workshop on Fixed Points in Computer Science, FICS 2010, Aug 2010, Brno, Czech Republic. pp.89. ⟨hal-00512377⟩
  • Alexander Shen, Laurent Bienvenu, Andrei Romashchenko. Sparse sets. JAC 2008, Apr 2008, Uzès, France. pp.18-28. ⟨hal-00274010⟩
  • Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed Point and Aperiodic Tilings. 12th International Conference on Developments in Language Theory, Sep 2008, Kyoto, Japan. pp.276-288, ⟨10.1007/978-3-540-85780-8_22⟩. ⟨hal-00256364v5⟩
  • Andrei Romashchenko. Reliable Computations Based on Locally Decodable Codes.. 23rd Annual Symposium on Theoretical Aspects of Computer Science, Feb 2006, Marseille, France. pp.537--548. ⟨hal-00293698⟩

Preprints, Working Papers, ...1 document

  • Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed-point tile sets and their applications. 2009. ⟨hal-00424024v5⟩