UC Irvine

The two-user computation broadcast problem is introduced as the setting where user 1 wants message W1 and has side information W0 1 , user 2 wants message W2 and has side information W0 2, and (W1;W0 1 ;W2;W0 2) may have arbitrary dependencies. The goal is to minimize the entropy H(S) of the broadcast information S that simultaneously satisfies both users' demands. It is shown that H(S) H(W1jW0 1) + H(W2jW0 2) min I(W1;W2;W0 2jW0 1 ); I(W2;W1;W0 1jW0 2 ) . Furthermore, for the linear computation broadcast problem, where W1;W0 1;W2;W0 2 are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight.