Description
Title: Uncertain Compression and Graph Coloring
Speaker: 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.