Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast

I. INTRODUCTION

• Extending approaches that optimize computation–communication tradeoffs for linearly separable computations to nonlinear tasks remains challenging.The cited approaches include work on distributed machine learning and coded matrix multiplication,, and computation–communication tradeoff methods –.Source: §I · p. 2
• NFCB is motivated by broadcast applications including coded caching, distributed computing, index coding, federated learning, and hypothesis testing.The introduction also connects the problem to multiple description coding, video broadcasting, cryptography, coordination, and synchronization.Source: §I · p. 2
• NFCB asks a sender with all datasets to broadcast one common message so users can recover their possibly nonlinear function demands using side information.Communication cost depends on the available side information and dependencies among data and functions.Source: §I · p. 2

A. Function Computation Broadcast and Known Instances

• The section identifies index coding, linear computation broadcast, and complementary delivery as known instances of function computation broadcast.Source: A. Function Computation Broadcast and… · p. 2
• The section places complementary delivery alongside index coding and linear computation broadcast as an instance of function computation broadcast.Source: A. Function Computation Broadcast and… · p. 2
• In index coding, a sender holds N independent datasets and serves K = N users.Source: 1) Index Coding · p. 2

1) Index Coding:

• Each index-coding user i requests X_i and has side information S_i drawn from other datasets.Source: 1) Index Coding · p. 2
• The side information graph is directed, with edge i → j indicating that user i knows dataset X_j.Source: 1) Index Coding · p. 2
• The minimum rank minrk_q(G) characterizes optimal scalar linear index-coding rate over F_q and lower-bounds the length of nonlinear index codes.For binary index coding, an optimal scalar linear code has length minrk_2(G) [20, Theorem 1].Source: 1) Index Coding · pp. 2–3
• Related extensions include multiple-sender index coding, cooperative data exchange, and functional index coding, where demands are functions of the datasets [33],,,.Source: 1) Index Coding · p. 3

2) Linear Computation Broadcast:

• Linear computation broadcast lets users request linear functions of the datasets, extending standard index coding demands –.Source: 2) Linear Computation Broadcast · p. 3
• With coded side information, the side information may be an arbitrary linear function of the datasets, and the task can be reformulated as generalized index coding with a minrank fitting-matrix problem.The fitting matrix captures subspace relations induced by demands and side information; the optimization is NP-hard.Source: 2) Linear Computation Broadcast · p. 3
• For the symmetric K-user setting, prior work gives the optimal rate when K > d and characterizes generic capacity within a factor of 2.Source: 2) Linear Computation Broadcast · p. 3
• For coded side information and all K ≥ 2, prior work gives the optimal linear vector index-code length, a generalization of matrix minrank that remains open in general.Source: 2) Linear Computation Broadcast · p. 3

3) Complementary Delivery:

• For two users with complementary side information, [42, Theorem 3] characterizes the optimal rate when demands are compatible or the datasets are binary.The cited result uses the f1f2-modified rook’s graph.Source: 3) Complementary Delivery · pp. 3–4
• Prior computation-broadcast results mainly cover linear computation or nonlinear complementary demands, often under strong structural assumptions or for specific user counts.Characterizing the optimal rate for general NFCB is at least as hard as general index coding; the paper aims to derive general upper and lower bounds.Source: 3) Complementary Delivery · p. 4

B. Contributions

• A characteristic-graph scheme handles arbitrary K, general source distributions, and finite-field demands without requiring linear or separable demands or linear encoding and decoding.The sender exploits the structure of the datasets and demanded functions.Source: B. Contributions · p. 4
• A side-information-assisted independent-set scheme is provided, and the optimal graph-based achievable rate is characterized for compatible functions.The latter characterization is Proposition 1.Source: B. Contributions · p. 5
• The converse results include a response-profile bound tighter than a basic side-information converse, clique-entropy bounds, and a genie-aided lower bound.The clique-entropy bounds address zero-error and asymptotically lossless operation using the operational block broadcast graph.Source: B. Contributions · p. 5
• The paper upper-bounds the average additive gap between the independent-set achievable rate and the genie-aided converse.The gap considered is between Corollary 1 and Proposition 2.Source: B. Contributions · p. 5
• For binary NFCB with linear or nonlinear demands, the converses are tight for several special topologies.These cases are given in Propositions 3, 4, and 5.Source: B. Contributions · p. 5
• Example 3 shows savings from nonlinear encoding over the best scalar and vector linear encodings.Proposition 7 also upper-bounds zero-error and asymptotically lossless operational broadcast entropies by linear-encoding performance.Source: B. Contributions · p. 5

C. Organization

• Section II presents the system model, and Section III develops achievability schemes using the operational block broadcast graph.The section outline identifies the operational block broadcast graph as the basis for the achievability discussion.Source: C. Organization · p. 5
• Sections IV and V develop converse bounds and analyze the average additive gap between the achievability scheme and genie-aided converse.The gap comparison is between Corollary 1 and Proposition 2.Source: C. Organization · p. 5
• Section VI compares the scheme with existing approaches through examples, and Section VII concludes and discusses future directions.Source: C. Organization · p. 5

II. SYSTEM MODEL

• The sender holds N datasets over a finite field, and user i has side information X_Ai and requests a function of the datasets.Users’ side information and demanded functions may be distinct, and the side information may be correlated with the demand.Source: §II · p. 6
• The length-n source consists of i.i.d. realizations whose dataset components may be arbitrarily dependent.Independence is across source realizations, not necessarily among the datasets within a realization.Source: §II · p. 6
• A rate is achievable when a sequence of codes makes the block error probability vanish as blocklength grows while approaching that rate.The system objective is to minimize the communication rate for asymptotically lossless recovery.Source: §II · pp. 7–8
• The sender broadcasts a common message, and each user may decode its demand using that message and its side information, with nonlinear operations allowed.The model imposes no computational constraint on the sender or users.Source: §II · p. 7

• The section gives an asymptotically lossless achievability scheme, a side-information-assisted independent-set scheme, and an optimal achievable-rate characterization for compatible demands.Source: §III · p. 8
• The broadcast graph generalizes characteristic graphs to jointly represent source statistics, user demands, and side-information-induced distinguishability for NFCB.The framework accommodates possibly non-linear demands.Source: §III · p. 10
• The operational block broadcast graph is generally neither an OR nor an AND power, because one fixed user must witness confusability across the entire block.That user must have identical side information throughout the block and different demand sequences.Source: §III · p. 11
• The OR-power graph can declare sequences adjacent even when no single user is operationally confused across the block; the graph-based bound is achievable but need not be optimal.The OR-power construction also grows exponentially with blocklength, making its computation impractical.Source: §III · pp. 10–12

Operational graph limitations

• The single-letter graph omits same-side-information, same-demand nonedges needed for the block graph, so ordinary OR or AND powers generally cannot recover it.Taking the union across users also loses which user generated each edge, so neither graph power generally commutes with the multi-user union.Source: §III · p. 12

Theorem 2

• Hκ(GB, X[N]) is achievable for asymptotically lossless recovery of all users’ demands.The construction uses a proper coloring of the OR power of the broadcast graph, which separates source-sequence pairs that are confusable for any user and permits exact demand recovery.Source: §III · p. 14

Proof of Theorem 2

• Random binning of an independent-set-valued sequence W^n yields vanishing error when R > Hq(W).Users decode from the bin index and their side information by identifying the unique typical sequence in the bin.Source: §III · pp. 14–15

R∗(K, N)

• The side-information-assisted independent-set scheme gives an achievable bound without requiring the users’ demands to be compatible.The construction uses a shared bin index to let users recover a selected W sequence from their side information, then reconstruct their demands symbolwise.Source: R∗(K, N) · pp. 15–16
• The single-letter conditional independent-set optimization does not generally characterize the operational multiletter broadcast graph entropy.The section notes that a multiletter gain is expected.Source: R∗(K, N) · p. 15
• Under compatibility, the stronger conclusion reduces the rate to the corresponding single-user converse bound.The passage states that the resulting achievable bound matches the corresponding single-user converse.Source: R∗(K, N) · pp. 16–17
• With compatible demands and S_i = X_i for every user, the section tightens the achievable bound using side-information-assisted chromatic entropy.The proposition states this conclusion subject to the compatibility condition.Source: R∗(K, N) · p. 16

Multi-letter response-profile converse

• Theorem 3’s multi-letter response-profile converse is tighter than a simple side-information-based converse, capturing each user’s demand and side information.Source: §IV · pp. 17, 18, 20

Clique-entropy converses

• Clique entropy yields zero-error and vanishing-error broadcast-rate converses that improve on a simple side-information converse.The bounds use the operational block broadcast graph, which is neither an OR nor an AND power of its single-letter counterpart.Source: §IV · pp. 20–22

Vanishing-error clique-entropy converse

• The vanishing-error clique-entropy converse evaluates graph quantities on a high-probability correct-decoding subset, and smoothing shows this restriction does not change the regularized bound.The smoothing result is stated for each blocklength and error parameter.Source: §IV · pp. 22–23

• The asymptotically lossless and zero-error settings share the same regularized clique-entropy converse, but it remains multiletter and has no known single-letter characterization.The graph-entropy tensorization results do not apply in the multi-user setting, although Lemma 1 eliminates the additional smoothing optimization.Source: §IV · pp. 23–24
• For two users, R*(K, N) ≥ max[Hq(f1 | X1) + Hq(f2 | X2, X1, f1), Hq(f2 | X2) + Hq(f1 | X1, X2, f2)].Source: §IV · p. 24
• For K users, the genie-aided lower bound maximizes over user permutations, revealing previously decoded demands to later users and charging their incremental conditional-entropy costs.The first user must receive at least Hq(fπ(1) | Sπ(1)) bits; each later user incurs a conditional-entropy cost given earlier decoded demands and side information.Source: §IV · p. 24
• Unlike Theorem 3's lower bound, the genie-aided bound incorporates interactions among the K users.Source: §IV · p. 25

Linear computation broadcast with linear encoding

• With linear demands and linear encoding/decoding, the MinRank formulation is optimal and the additive gap is zero for every K≥2.Source: §V · p. 25

Recovering all datasets

• When every user requests all datasets it lacks, Slepian–Wolf coding achieves the minimum sum-rate in (11).This applies when each user's side information is a subset of the datasets.Source: §V · p. 25

Complementary side information with K=N=2

• For K=N=2 with complementary side information, R*(2,2)=max(Hq(f1 | X1), Hq(f2 | X2)) is optimal when the functions are compatible or q=2.The proposed scheme achieves this optimal rate, previously proven in [42, Theorem 3].Source: §V · p. 25

K=N=3 additive-gap bound

• For binary K=N=3, the worst-case gap is at most 0.5 bits, while the average gap is 0.125 bits when all topologies are equally likely.The worst case reaches 0.5 bits for some topology.Source: §V · p. 30

K=N=4 additive-gap bound

• For binary K=N=4, Proposition 5 considers the worst-case additive gap over all possible topologies, but the supplied passage does not give its bound.Source: §V · p. 30

V. ADDITIVE GAP BETWEEN THE ACHIEVABLE RATE AND THE GENIE-AIDED BOUND

• For four users, Δ(4,4) is bounded by H2(W | f1, X1) minus the largest two-step conditional-demand entropy sum over permutations of the remaining users.The subtracted terms are H2(fi2 | X1, Xi2, f1) and H2(fi3 | X1, Xi2, Xi3, f1, fi2).Source: §V · p. 31
• The four-user gap analysis conditions the broadcast graph on (X1, f1) and constructs further graphs conditioned on users’ side information.The conditional graph entropies are used to characterize Δ(4,4).Source: §V · pp. 31, 33
• 0.25 bits bounds Δ(4,4), using the average over equally likely topologies and Δ(3,3) = 0.125 bits.The four-user average gap is bounded by 2Δ(3,3).Source: §V · p. 33
• Determining the optimality gap for general (K, N), general side information, and q ≥ 2 remains an open problem.Source: §V · p. 33

VI. EXAMPLES ON (K = 3, N = 3)-COMPUTATION BROADCAST

• Example 3 shows nonlinear encoding can outperform scalar and vector linear encoding, while Proposition 7 upper-bounds operational broadcast entropies by linear-encoding performance.The section introduction attributes these claims to Propositions 6 and 7.Source: §VI · p. 34
• For the Boolean-demand example, the conditional characteristic-graph entropies are 0.406 bits for f1, 0.406 bits for f2, and 0.906 bits for f3.The reported universal lower bound is 0.906 bits; the passage notes it can be strict when the functions are incompatible.Source: §VI · pp. 34–35

0.25 (see Figure 7 (Left) for GB). Hence, from (20)

• For this Boolean example, minimum-entropy coloring gives H2(W) = 1.5 bits, while the single-letter clique entropy is 1.417 bits and does not tensorize into an operational converse.The text says the coloring solution is not optimal and can be tightened using a multiletter graph followed by Slepian-Wolf coding.Source: §0.25 · pp. 36–38
• The genie-aided bound gives R*(3, 3) ≥ 1.155 bits, and the text contrasts it with the earlier bound as tighter than Proposition 2.The cited passage reports the bound as the sum of three conditional entropies.Source: §0.25 · p. 38

ii) Compatibility function-based approach

• Pairwise compatible functions each cost 1 bit, and splitting every dataset into two subsymbols enables three joint transmissions to recover all users’ demands.The scheme decodes f1 from the first and third transmissions, f2 from the first and second, and f3 from the second and third.Source: §0.25 · p. 39

iii) Broadcast graph approach

• The broadcast graph has 225 maximal independent sets: 162 of size four and 63 of size three; its side-information-assisted graph entropy is 1.667 trits.The entropy-optimizing distribution assigns positive probability to disjoint maximal independent sets.Source: §0.25 · pp. 39–40
• For broadcast graph GB with X[3], Hκ(GB, X[3]) = 1.738 trits and Hω(GB, X[3]) = 1.262 trits; α(GB) = ω(GB) = 4 and χ(GB) = 7, so GB is not perfect.Source: §0.25 · p. 40

Block-graph bounds

• For block graphs, a 27-color splitting construction gives an exact two-letter result, while the stated three-letter splitting construction uses five ternary transmissions.The passages do not provide the corresponding rates in full.Source: §0.25 · p. 41
• Linear splitting achieves rate 1.5 on even blocklengths and an upper bound approaching 1.5 from above on odd blocklengths; larger non-linear independent sets are not ruled out.The exact asymptotic independence-number exponent remains open, so the bounds do not establish the regularized Körner entropy as 1.Source: §0.25 · pp. 41–42

ii) Compatibility function-based approach

• 1 ≤ R*(3,3) ≤ R*0(3,3) ≤ RCompat.(3,3) = 1.5 < 1.667, the side-information-assisted graph-entropy rate; the genie-aided lower bound of 1 is not tight.The conditional graph entropy is Hκ(GB | Xi) = 1.667 trits. The compatible-function rate improves on this scheme.Source: §0.25 · pp. 40, 42

Example 2

• The example demonstrates a strict multiletter gain: the single-letter conditional independent-set expression need not tensorize and is only an achievable bound.The union-graph operation loses which user creates each edge, while vector linear coding can exploit cross-coordinate alignment.Source: §0.25 · p. 43
• A data-splitting linear vector scheme that exploits source statistics reduces average broadcast length relative to (43).The scheme builds on the fixed-length minrank framework.Source: §0.25 · p. 43

Example 3

• A scalar nonlinear zero-error encoder uses six binary transmissions, while no scalar or vector linear encoder over F2 attains rate 6.The strict improvement is entirely due to nonlinear broadcast encoding.Source: §0.25 · pp. 44–45
• The example’s zero-error and asymptotically lossless operational broadcast entropies coincide, and its optimal rate is 6 under the uniform source distribution.The six-bit construction achieves the zero-error rate, while a genie-aided converse gives the matching asymptotic lower bound.Source: §0.25 · pp. 45–46
• For the 26-user example, characteristic-graph encoding assigns codewords to maximum independent sets and reduces average code length over scalar and vector linear encoding [70].The passage notes that deriving order-optimal nonlinear encoding mappings remains open.Source: §0.25 · p. 46

Example 4

• In the three-user Boolean example, the broadcast graph is self-complementary, and the scheme in Theorem 2 achieves the optimum.The instance uses three Boolean sources and the demands specified in (206).Source: §0.25 · p. 46

VI. EXAMPLES ON (K = 3, N = 3)-COMPUTATION BROADCAST

• The optimal one-shot zero-error rate is log2 χ(GB) = log2 3 = 1.585 bits, with α(GB) = ω(GB) = χ(GB) = 3.Source: §0.25 · p. 47
• Conditioning the graph on X1 gives Hχ(GB, X[3] | X1) = 1.5 bits, whereas conditioning on X2 or X3 gives 1 bit.Source: §0.25 · p. 48
• Because f1 is independent of X1, H2(f1 | X1) = 1.5 bits, yielding a single-user converse of at least 1.5 bits.The passage also states that the Körner-entropy upper bound and the single-user converse coincide.Source: §0.25 · p. 48
• The proposed technique achieves the 1.5-bit asymptotic optimum, with the operational quantities coinciding in this self-complementary perfect-graph example.The stated equality is R*(3, 3) = Hκ(GB, X[3]) = HSIχ,B(GB, X[3] | S[3] = X[3]) = 1.5.Source: §0.25 · p. 48

VII. CONCLUSION

• The characteristic-graph scheme reduces communication rate compared with the state of the art while accommodating linear and non-linear demands.It designs the broadcast message as a function of each user’s desired function and side information.Source: §VII · p. 48
• Theorem 3 gives tighter converses than a simple side-information converse by capturing each user’s demand and side information.Its bound is compared with the achievable rate, which optimizes a coloring distribution over broadcast-graph independent sets.Source: §VII · p. 48
• Theorem 4 and Theorem 5 give entropy-based converses using the length-n operational block broadcast graph G(n).These bounds use the graph formed for the operational block.Source: §VII · p. 48
• The achievable-to-converse gap is tight under certain broadcast-graph structural properties, and the achievable rate is optimal for compatible functions.The paper also states that further work is needed to sharpen the bounds and quantify fundamental rate limits.Source: §VII · p. 49