?
One-Sided Error Communication Complexity of Gap Hamming Distance
P. 1–15.
Klenin E., Козачинский А. Н.
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Vol. 117. , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018.
Верещагин Н. К., Дектярев М. В., Математический сборник 2025 Т. 216 № 6 С. 3–45
Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...
Добавлено: 23 августа 2025 г.
Игнатьев А. А., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.
Добавлено: 9 ноября 2023 г.
Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160
Добавлено: 20 августа 2021 г.
Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26
Добавлено: 23 декабря 2020 г.
Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660
Добавлено: 15 марта 2018 г.
Козачинский А. Н., Theory of Computing Systems 2018 Vol. 62 No. 3 P. 583–599
In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability ε). Instead of one-way transmission we allow them to interact. They may also ...
Добавлено: 9 февраля 2017 г.
Козачинский А. Н., , in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, ProceedingsVol. 9691: Lecture Notes in Computer Science.: Switzerland: Springer, 2016. P. 207–222.
In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability εε). Instead of one-way transmission we ...
Добавлено: 16 сентября 2016 г.
Brody J., Buhrman H., Koucký M. и др., Algorithmica 2016 Vol. 76 No. 3 P. 749–781
Добавлено: 2 марта 2016 г.
Козачинский А. Н., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.
Добавлено: 29 февраля 2016 г.
Hansen K. A., Подольский В. В., Information and Computation 2015 Vol. 240 P. 56–73
Добавлено: 30 мая 2015 г.
Верещагин Н. К., , in: CSR 2014 : 9th International Computer Science Symposium in Russia. ProceedingsVol. 8476.: Berlin: Springer, 2014. P. 365–374.
Добавлено: 6 октября 2014 г.
Верещагин Н. К., / Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178.
Добавлено: 14 декабря 2013 г.
Brody J., Buhrman H., Koucky M. и др., / Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR12-179.
Добавлено: 14 декабря 2013 г.
Proceedings of the First International Conference on Data Compression, Communications and Processing
NY: IEEE Computer Society, 2013.
This book constitutes the refereed proceedings of the First International Conference on Data Compression, Communications and Processing held in Palinuro, Italy, in June 2011. ...
Добавлено: 30 октября 2013 г.