Deterministic compression with uncertain priors
Elad Haramaty, Madhu Sudan · 2014
Communication in "natural" settings, e.g., between humans, is distinctly different than that in classical designed settings, in that the former is 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 reciever that can compress information down roughly to its entropy.