Skip to main content
eScholarship
Open Access Publications from the University of California

The Capacity of Linear Computation Broadcast

  • Author(s): Sun, H
  • Jafar, SA
  • et al.
Abstract

© 2019 IEEE. 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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View