Uncertain Compression and Graph Coloring

Madhu Sudan (Harvard)

The classical task of compression, made famous by the works of Shannon and Huffman, asks the question: Given a distribution on possible messages, how can one build a dictionary to represent the messages so as to (approximately) minimize the expected length of the representation of a random message sampled from this distribution.  Given the centrality of compression as a goal in all, natural or designed, communication, we introduce and study the uncertain compression problem. Here the goal is to design a compression scheme that associates a dictionary to each distribution such that messages can be recovered even by receivers that do not know the distribution exactly, but only know them approximately. Understanding the limits of uncertain compression leads to intriguing challenges and in particular leads to the challenge of understanding the chromatic number of an explicit family of graphs. In this talk we will describe some of the graphs, and attempts to bound their chromatic number.

Based on joint works with Badih Ghazi, Elad Haramaty, Brendan Juba, Adam Kalai, Pritish Kamath and Sanjeev Khanna.