  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}}\leq
H(W_1,W_2)/\left[H(W_1|W_1')+H(W_2|W_2')-\min\Big(I(W_1; W_2, W_2'|W_1'),
I(W_2; W_1, W_1'|W_2')\Big)\right]$. 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.
