On the Capacity of Computation Broadcast
share
The two-user computation broadcast problem is introduced as the setting where User 1 wants message W_1 and has side-information W_1', User 2 wants message W_2 and has side-information W_2', and (W_1, W_1', W_2, W_2') may have arbitrary dependencies. The rate of a computation broadcast scheme is defined as the ratio H(W_1,W_2)/H(S), where S is the information broadcast to both users to simultaneously satisfy their demands. The supremum of achievable rates is called the capacity of computation broadcast C_CB. It is shown that C_CB≤ H(W_1,W_2)/[H(W_1|W_1')+H(W_2|W_2')-(I(W_1; W_2, W_2'|W_1'), I(W_2; W_1, W_1'|W_2'))]. For the linear computation broadcast problem, where W_1, W_1', W_2, W_2' are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight. For non-linear computation broadcast, it is shown that this bound is not tight in general. Examples are provided to prove that different instances of computation broadcast that have the same entropic structure, i.e., the same entropy for all subsets of {W_1,W_1',W_2,W_2'}, can have different capacities. Thus, extra-entropic structure matters even for two-user computation broadcast. The significance of extra-entropic structure is further explored through a class of non-linear computation broadcast problems where the extremal values of capacity are shown to correspond to minimally and maximally structured problems within that class.
READ FULL TEXT