  A sender holds a word x consisting of n blocks x_i, each of t bits, and
wishes to broadcast a codeword to m receivers, R_1,...,R_m. Each receiver R_i
is interested in one block, and has prior side information consisting of some
subset of the other blocks. Let \beta_t be the minimum number of bits that has
to be transmitted when each block is of length t, and let \beta be the limit
\beta = \lim_{t \to \infty} \beta_t/t. In words, \beta is the average
communication cost per bit in each block (for long blocks). Finding the coding
rate \beta, for such an informed broadcast setting, generalizes several coding
theoretic parameters related to Informed Source Coding on Demand, Index Coding
and Network Coding.
  In this work we show that usage of large data blocks may strictly improve
upon the trivial encoding which treats each bit in the block independently. To
this end, we provide general bounds on \beta_t, and prove that for any constant
C there is an explicit broadcast setting in which \beta = 2 but \beta_1 > C.
One of these examples answers a question of Lubetzky and Stav.
  In addition, we provide examples with the following counterintuitive
direct-sum phenomena. Consider a union of several mutually independent
broadcast settings. The optimal code for the combined setting may yield a
significant saving in communication over concatenating optimal encodings for
the individual settings. This result also provides new non-linear coding
schemes which improve upon the largest known gap between linear and non-linear
Network Coding, thus improving the results of Dougherty, Freiling, and Zeger.
  The proofs use ideas related to Witsenhausen's rate, OR graph products,
colorings of Cayley graphs and the chromatic numbers of Kneser graphs.
