Broadcasting with Side Information

The problem of broadcasting with side information begins with a set of users, a single sender, and a set of messages. Each user already possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate, ., the average communication cost for sufficiently long broadcasts.

Any graph G =(V,E) describes an instance of a broadcasting with side information problem with n messages: x1, x2, ..., xn, and n users, where user i desires message xi and already knows messages j such that (i,j) is an edge in G.  The graph parameter .(G) is the optimal broadcast rate of the instance given by G.

It is known that .(G) lies between the independence number of G and the chromatic number of the complement of G.  We show, using an information theoretic linear program and ideas from Ramsey theory, that there can be polynomial separations between the three parameters.  Further, the same analysis tools are the basis for showing a polynomial separation between the vector linear and non-linear broadcast rate, and also for computing the broadcast rate exactly for classes of graphs. 

Joint work with Robert Kleinberg(Cornell) and Eyal Lubetzky (Microsoft Research, Redmond)