On Slepian–Wolf Theorem with Interaction

A. Kozachinskiy

doi:10.1007/978-3-319-34171-2_15

Публикации

?

On Slepian–Wolf Theorem with Interaction

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 allow them to interact. They may also use shared randomness.

Язык: английский

DOI

Текст на другом сайте

Ключевые слова: communication complexity Information complexity Slepian–Wolf theorem

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Теоретическая информатика (2016)

В книге

Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings

Vol. 9691: Lecture Notes in Computer Science. , Switzerland: Springer, 2016.

Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Верещагин Н. К., Дектярев М. В., Математический сборник 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 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., 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 г.

Counting the Number of Perfect Matchings, and Generalized Decision Trees

Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160

Добавлено: 20 августа 2021 г.

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26

Добавлено: 23 декабря 2020 г.

One-Sided Error Communication Complexity of Gap Hamming Distance

Klenin E., Козачинский А. Н., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.

Добавлено: 28 августа 2018 г.

Euclidean Distance Matrices and Separations in Communication Complexity Theory

Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660

Добавлено: 15 марта 2018 г.

On Slepian–Wolf Theorem with Interaction

Козачинский А. Н., 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 г.

Towards a Reverse Newman’s Theorem in Interactive Information Complexity

Brody J., Buhrman H., Koucký M. и др., Algorithmica 2016 Vol. 76 No. 3 P. 749–781

Добавлено: 2 марта 2016 г.

Making Randomness Public in Unbounded-Round Information Complexity

Козачинский А. Н., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.

Добавлено: 29 февраля 2016 г.

Polynomial threshold functions and Boolean threshold circuits

Hansen K. A., Подольский В. В., Information and Computation 2015 Vol. 240 P. 56–73

Добавлено: 30 мая 2015 г.

Randomized communication complexity of approximating Kolmogorov complexity

Верещагин Н. К., , in: CSR 2014 : 9th International Computer Science Symposium in Russia. ProceedingsVol. 8476.: Berlin: Springer, 2014. P. 365–374.

Добавлено: 6 октября 2014 г.

Randomized communication complexity of appropximating Kolmogorov complexity

Верещагин Н. К., / Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178.

Добавлено: 14 декабря 2013 г.

Towards a Reverse Newman's Theorem in Interactive Information Complexity

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 г.