Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.13464 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914357002108928 |
|---|---|
| author | Padda, Gurleen Touchette, Dave |
| author_facet | Padda, Gurleen Touchette, Dave |
| contents | There is a close relationship between the communication complexity and information complexity of communication problems, as demonstrated by results such as Shannon's noiseless source coding theorem, and the Slepian-Wolf theorem. Here, we study this relationship in the prior-free and interactive setting, where we provide an alternate proof for the result of Braverman [SIAM Review, vol. 59, no. 4, 2017], that the amortized communication complexity of simulating a prior-free interactive communication protocol, is equal to its prior-free information cost. While this is a known result, our approach addresses the need for a more natural proof of it. We also improve on the result by achieving round preservation, and using a bounded quantity of shared randomness. We do this by showing that the communicating parties can produce a reliable estimate of the joint type, or empirical distribution, of their inputs. This estimate is then used in our protocol for the prior-free reverse Shannon theorem with side information at the receiver. These results are then generalized to the interactive setting to obtain our main result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13464 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Round-Preserving Asymptotic Compression of Prior-Free Interactive Protocols Padda, Gurleen Touchette, Dave Information Theory There is a close relationship between the communication complexity and information complexity of communication problems, as demonstrated by results such as Shannon's noiseless source coding theorem, and the Slepian-Wolf theorem. Here, we study this relationship in the prior-free and interactive setting, where we provide an alternate proof for the result of Braverman [SIAM Review, vol. 59, no. 4, 2017], that the amortized communication complexity of simulating a prior-free interactive communication protocol, is equal to its prior-free information cost. While this is a known result, our approach addresses the need for a more natural proof of it. We also improve on the result by achieving round preservation, and using a bounded quantity of shared randomness. We do this by showing that the communicating parties can produce a reliable estimate of the joint type, or empirical distribution, of their inputs. This estimate is then used in our protocol for the prior-free reverse Shannon theorem with side information at the receiver. These results are then generalized to the interactive setting to obtain our main result. |
| title | Round-Preserving Asymptotic Compression of Prior-Free Interactive Protocols |
| topic | Information Theory |
| url | https://arxiv.org/abs/2507.13464 |