Graph-theoretic bounds for non-linear function computation broadcast

This work studies non-linear function computation broadcast (NFCB), in which a sender with access to N datasets (X1,...,XN) broadcasts a common message to K users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner’s characteristic-graph framework, we develop an achievable scheme for arbitrary K, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independentset scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with N = K and side information Xi at user i, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for K = 3 and K = 4. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.