Deterministic Compression with Uncertain Priors
Deterministic Compression with Uncertain Priors
复制标题
具有不确定先验的确定性压缩
DOI：
10.1007/s00453-015-0107-6
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
M. Sudan
中科院分区：
文献类型：
--
作者：
Elad Haramaty;M. Sudan
在“自然”环境下的交流，例如人与人之间的交流，与在经典设计环境下的交流有明显的不同，因为前者的特征总是发送者和接收者彼此并不完全一致。因此，经典通信问题的解决方案必须克服由于缺乏事先协议而引入的额外不确定性层。通信的经典目标之一是压缩信息，在这种情况下，缺乏一致性意味着发送方和接收方可能无法就生成信息的“先验”达成一致。当发送方和接收方不同意先验时，大多数经典的压缩机制都是非鲁棒的。Juba等人（Proc. ITCS 2011）表明，确实存在发送方和接收方之间具有共享随机性的压缩方案，这些压缩方案不共享可以将信息大致压缩到其熵的先验。在这项工作中，我们探讨了发送者和接收者之间共享随机性的假设，并强调了为什么这个假设在处理自然通信时是有问题的。我们在不确定的先验条件下开始了确定性压缩方案的研究，并揭示了这个问题的一些数学方面。我们给出了一些非平凡的确定性压缩方案，以及压缩方案自然类的一些下界。我们表明，对确定性通信的充分理解在图论和通信复杂性方面变成了具有挑战性的（开放的）问题。
Communication in “natural” settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the “prior” from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity.