Zobrazeno 1 - 10
of 35
pro vyhledávání: '"Andrei Romashchenko"'
Autor:
Alexander Shen, Andrei Romashchenko
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 90, Iss Proc. AUTOMATA&JAC 2012, Pp 127-132 (2012)
We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial
Externí odkaz:
https://doaj.org/article/cf5819c84e654b95b3117da2277af04e
The paper proposes open problems in classical Kolmogorov complexity. Each problem is presented with background information and thus the article also surveys some recent studies in the area.
Comment: The paper has appeared in the Open Problems co
Comment: The paper has appeared in the Open Problems co
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f378e9cdedb950a11e3a6106fa583c6
http://arxiv.org/abs/2203.15109
http://arxiv.org/abs/2203.15109
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (H
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37a3b36cd09bc396ad4c1d2a92ae67ff
http://arxiv.org/abs/2010.10221
http://arxiv.org/abs/2010.10221
Autor:
Emirhan Gürpınar, Andrei Romashchenko
Publikováno v:
IEEE International Symposium on Information Theory
2019 IEEE International Symposium on Information Theory (ISIT)
2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019, Paris, France. pp.1377-1381, ⟨10.1109/ISIT.2019.8849309⟩
ISIT 2019-IEEE 1st International Symposium on Information Theory
ISIT 2019-IEEE 1st International Symposium on Information Theory, Jul 2019, Paris, France. pp.1377-1381, ⟨10.1109/ISIT.2019.8849309⟩
ISIT
2019 IEEE International Symposium on Information Theory (ISIT)
2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019, Paris, France. pp.1377-1381, ⟨10.1109/ISIT.2019.8849309⟩
ISIT 2019-IEEE 1st International Symposium on Information Theory
ISIT 2019-IEEE 1st International Symposium on Information Theory, Jul 2019, Paris, France. pp.1377-1381, ⟨10.1109/ISIT.2019.8849309⟩
ISIT
We discuss linear programming techniques that help to deduce corollaries of non classic inequalities for Shannon's entropy. We focus on direct applications of the copy lemma. These applications involve implicitly some (known or unknown) non-classic u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9361f67aab8a690bd5e49296bfd65cc0
http://arxiv.org/abs/1901.07476
http://arxiv.org/abs/1901.07476
Autor:
Julien Destombes, Andrei Romashchenko
Publikováno v:
STACS 2019-36th International Symposium on Theoretical Aspects of Computer Science
STACS 2019-36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩
36th International Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩
STACS 2019-36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩
36th International Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩
We suggest necessary conditions of soficness of multidimensional shifts formulated in termsof resource-bounded Kolmogorov complexity. Using this technique we provide examples ofeffective and non-sofic shifts on $\mathbb{Z}^2$ with very low block comp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::81269322ee3be2f3f4185ad9c6c978d9
Autor:
Andrei Romashchenko, Daniyar Chumbalov
Publikováno v:
IEEE Transactions on Information Theory
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054-6069. ⟨10.1109/TIT.2018.2854589⟩
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054-6069. ⟨10.1109/TIT.2018.2854589⟩
We study the following combinatorial version of the Slepian-Wolf coding scheme. Two isolated Senders are given binary strings $X$ and $Y$ respectively; the length of each string is equal to $n$, and the Hamming distance between the strings is at most
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a91aa89ce72ca29062061a8c4786c7d8
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233020
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233020
Publikováno v:
IEEE Transactions on Information Theory
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩
We show that the inequality $H(A | B,X) + H(A | B,Y) \leqslant H(A | B)$ for jointly distributed random variables $A,B,X,Y$ , which does not hold in general case, holds under some natural condition on the support of the probability distribution of $A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::11a13b0377d2992dff6eca31e31773e7
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793775
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793775
Autor:
Andrei Romashchenko, Marius Zimand
Publikováno v:
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2019, 66 (5), pp.1-42. ⟨10.1145/3356867⟩
45th International Colloquium on Automata, Languages, and Programming
ICALP: International Colloquium on Automata, Languages, and Programming
ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. pp.95:1-95:14, ⟨10.4230/LIPIcs.ICALP.2018.95⟩
Journal of the ACM (JACM), Association for Computing Machinery, 2019, 66 (5), pp.1-42. ⟨10.1145/3356867⟩
45th International Colloquium on Automata, Languages, and Programming
ICALP: International Colloquium on Automata, Languages, and Programming
ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. pp.95:1-95:14, ⟨10.4230/LIPIcs.ICALP.2018.95⟩
We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings $x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having $x$ and the complexity p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cf7cf4b70732ca45e68b8e2b8a4ba92f
Autor:
Bruno Durand, Andrei Romashchenko
Publikováno v:
Ergodic Theory and Dynamical Systems
Ergodic Theory and Dynamical Systems, Cambridge University Press (CUP), 2021, 41 (4), pp.1086-1138. ⟨10.1017/etds.2019.112⟩
Ergodic Theory and Dynamical Systems, Cambridge University Press (CUP), 2021, 41 (4), pp.1086-1138. ⟨10.1017/etds.2019.112⟩
We study multidimensional minimal and quasiperiodic shifts of finite type. We prove for these classes several results that were previously known for the shifts of finite type in general, without restriction. We show that some quasiperiodic shifts of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b98b63c2fa7e24cac75b1ef6daef6efc
Publikováno v:
34th Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩
The Journal of Symbolic Logic
The Journal of Symbolic Logic, Association for Symbolic Logic, In press, pp.1-41. ⟨10.1017/jsl.2019.53⟩
The Journal of Symbolic Logic, Association for Symbolic Logic, 2020, 85 (2), pp.632-670. ⟨10.1017/jsl.2019.53⟩
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩
The Journal of Symbolic Logic
The Journal of Symbolic Logic, Association for Symbolic Logic, In press, pp.1-41. ⟨10.1017/jsl.2019.53⟩
The Journal of Symbolic Logic, Association for Symbolic Logic, 2020, 85 (2), pp.632-670. ⟨10.1017/jsl.2019.53⟩
In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initia
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1f5e331c039ddd67ab31b064932551e3