

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。