Source-linked AI summary
Broadcasting with side information
Noga Alon, Avinatan Hasidim, Eyal Lubetzky, Uri Stav, Amit Weinstein
TL;DR
The paper studies informed broadcast coding with receiver side information, focusing on whether large blocks and disjoint instances reduce communication beyond single-bit coding. It formalizes the setting with directed hypergraphs and analyzes codes through confusion graphs, OR products, and graph colorings. It proves explicit families with β*(H)/k<3 while β_1(H)>C, β(H)=2 with β_1(H)>C, and further network-coding separations.
Problem
The paper asks how communication changes when receivers demand individual blocks, possess side information, and blocks or broadcast settings are repeated.
Method
It models receivers with directed hypergraphs and studies optimal codes using confusion graphs, OR graph products, Cayley-graph structure, and fractional coloring.
Results
For every large constant C, explicit families satisfy β*(H)/k<3 while β_1(H)>C; another family has β(H)=2 while β_1(H)>C.
Takeaways & Limitations
Large blocks and combined independent broadcast settings can outperform bitwise or separately concatenated optimal encodings, while the constructions improve known linear-versus-non-linear network-coding gaps.
Takeaways & Limitations
The paper notes that no better upper bound specific to confusion graphs is known for the gap, whose general upper bound is Θ(n).
Abstract
from arXiv · showhide
A sender holds a word x consisting of n blocks x_i, each of t bits, and wishes to broadcast a codeword to m receivers, R_1,...,R_m. Each receiver R_i is interested in one block, and has prior side information consisting of some subset of the other blocks. Let β_t be the minimum number of bits that has to be transmitted when each block is of length t, and let βbe the limit β= \lim_{t \to \infty} β_t/t. In words, βis the average communication cost per bit in each block (for long blocks). Finding the coding rate β, for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding. In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on β_t, and prove that for any constant C there is an explicit broadcast setting in which β= 2 but β_1 > C. One of these examples answers a question of Lubetzky and Stav. In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of Dougherty, Freiling, and Zeger. The proofs use ideas related to Witsenhausen's rate, OR graph products, colorings of Cayley graphs and the chromatic numbers of Kneser graphs.
1 Introduction
The paper studies informed broadcast coding for block-based data with receiver side information, formalized by directed hypergraphs and asymptotic broadcast rates. It establishes bounds and explicit separations showing that large blocks and disjoint unions can substantially outperform single-bit or separately concatenated codes.
- Problem formulation: Each receiver seeks one block while using a specified subset of other blocks as side information, and the sender must enable every receiver to reconstruct its missing block.The setting models applications such as Video on Demand and generalizes Index Coding and Network Coding.
- Problem formulation: Directed hypergraphs represent broadcast settings: vertices are input blocks, and directed edges encode receivers’ demanded blocks and known blocks.The quantity β_t(H) is the minimum broadcast length when every block has t bits.
- Broadcast rate: Sub-additivity of β_t(H) implies that β(H)=lim_t→∞ β_t(H)/t exists and equals inf_t β_t(H)/t.β is the asymptotic average number of encoding bits required per bit in each input block.
- General bounds: β(H) ≤ β*(H), because receivers handling large blocks possess additional information compared with independent replicated single-bit instances.The comparison follows by viewing each receiver as t receivers, each interested in one bit.
- Direct-sum phenomena: For the odd-cycle network on five vertices, β_1(H)=3 whereas β*(H)=5−log2 5≈2.68, with limiting copies requiring 6.4 codewords versus 8 for one copy.The direct-sum improvement persists beyond integer-rounding effects and generalizes to complements of odd cycles.
- Main separations: For an explicit infinite family, β*(H) < 3 remains bounded while β_1(H) is unbounded, and another family has β(H)=2 while β*(H) is unbounded.These results show that large blocks can strictly improve communication over bitwise coding.
- Network-coding implications: The constructions also yield a 48-vertex network whose coding-capacity to linear-capacity ratio is at least 1.324.For a related hypergraph, every linear code requires 3 bits while β*(H)≤2.265.
2 Optimal codes for a disjoint union of directed hypergraphs
The paper converts optimal broadcast coding for disjoint hypergraphs into graph coloring, then analyzes repeated disjoint instances through OR graph products and fractional chromatic numbers. This framework connects codeword growth to independence numbers and yields asymptotic formulas.
- Confusion graphs: For block length t=1, two input words are confusable when some receiver cannot distinguish their demanded bits using identical side information.The confusion graph C(H) places all binary input words at its vertices and joins confusable pairs.
- Confusion graphs: A broadcast code is equivalent to a legal coloring of C(H), so the optimal number of codewords equals χ(C(H)).Each color class consists of inputs that can share one codeword without decoding ambiguity.
- Disjoint unions: The confusion graph of a disjoint union satisfies C(H1+H2)≅C(H1)∨C(H2), where adjacency in the OR product occurs if either component is adjacent.Therefore, k disjoint copies correspond to the k-fold OR product C(H)∨k.
- Disjoint unions: The optimal code for k·H has as many codewords as χ(C(H)∨k), linking repeated broadcast instances to chromatic numbers of OR graph powers.This places the problem alongside graph-capacity questions related to Shannon capacity and Witsenhausen’s rate.
- Asymptotic rate: Because C(H) is a vertex-transitive Cayley graph and γ equals its independence number, fractional coloring determines the asymptotic codeword rate for repeated disjoint copies.The resulting relation is expressed through α(C(H)) and the asymptotic behavior of β*(H).
3 The possible gaps between the parameters β, β∗and β1
This section constructs broadcast settings where the asymptotic rate β, disjoint-union rate β∗, and one-bit rate β1 differ substantially. The constructions use confusion graphs, Cayley graphs, Hamming codes, and Kneser graphs to establish these gaps and their coding consequences.
- Gap constructions: β = 2 while β∗ and β1 are both Θ(log n) for an explicit family with n = 2^k vertices.This is the first construction separating the asymptotic rate from the other two parameters.
- Gap constructions: β∗ < 3 while β1 = Θ(log log n) for a more general explicit family of directed hypergraphs.The construction gives a bounded disjoint-union rate alongside a growing one-bit rate.
- First construction: χ(C_t) = χf(C_t) = 2^(2t) when 2^t ≥ n, yielding the block-length behavior used to complete the first construction.The lower bound comes from a clique, and the upper bound from a two-coordinate Reed–Solomon coloring.
- Cayley-graph construction: For any Abelian Cayley graph G, the associated confusion graph C satisfies χ(G) ≤ χ(C) ≤ 3χ(G) and χf(G) ≤ χf(C) ≤ 3χf(G).These bounds transfer chromatic gaps from Cayley graphs to confusion graphs.
- Network Coding applications: A network of size 48 has optimal code rate β ≤ β∗ ≤ log2 4.809 ≈ 2.265, while every linear code requires length at least 3, giving ratio 1.324.This provides an explicit linear-versus-nonlinear Network Coding separation.
4 Conclusions and open problems
The conclusions show that large blocks and jointly encoded independent instances can substantially reduce broadcast cost, while leaving open sharper bounds and broader network-coding separations.
- β∗(H)/k < 3 while β1(H) > C for suitable examples and every large constant C.These examples demonstrate an arbitrarily large gap between single-bit and asymptotic replicated-instance costs.
- Encoding an entire block at once can outperform concatenating optimal single-bit codes, motivating the asymptotic broadcast rate β(H).The rate measures the asymptotic average number of transmitted bits per bit in each block.
- Multiple users requesting the same block enable hypergraphs whose confusion graphs exhibit larger gaps.This generalizes the setting used for the earlier constructions.
- For some families, the ratio between the relevant costs reaches Θ(log n), while large t-bit blocks require only a quantity linear in t.For another family, t independent copies require a number of bits linear in t.
- The Cayley-graph construction preserves the original graph’s gap, whose maximum obtainable size is O(log n).This follows the general maximum gap between fractional and integer chromatic numbers for n-vertex graphs.
- The confusion-graph gap remains far below the general Θ(log V)=Θ(n) upper bound, and no sharper confusion-graph-specific upper bound is known.The paper also identifies arbitrarily large linear-versus-nonlinear Network Coding gaps as an open question under field-independent network constructions.
A.1 Proof of Theorem 3.15
The proof establishes that every matrix fitting the odd-cycle complement C2n+1 has rank at least 3, completing Theorem 3.15.
- A fitting matrix has nonzero diagonal entries and unrestricted entries only where the graph permits edges.The minimum rank of such fitting matrices lower-bounds the length of a linear encoding.
- rank(A) ≥ 3 for every matrix fitting C2n+1 over any field F.This is the central claim used in the theorem’s proof.
- Assuming rank(A)=2 expresses every row as a linear combination of the first two rows.The proof then inductively forces the coefficient of one basis row to vanish on alternating indices.
- The alternating coefficient constraints make the final row proportional to the first, contradicting its zero entry in column 1.Thus rank 2 is impossible.
- Claim A.1 completes the proof of Theorem 3.15.
A.2 Complements of odd cycles
The section establishes monotonicity properties for fractional and integer chromatic numbers of confusion graphs associated with complements of odd cycles, yielding persistent gaps between them.
- The 5-cycle is the smallest graph whose confusion graph has different fractional and integer chromatic numbers.
- Independent sets can be extended from C2n+1 to C2n+3 by a factor of four, preserving the structure needed for the construction.The extension maps each vertex to four vertices and forms the union over an independent set.
- The fractional chromatic number is monotone decreasing with n: χf(C2n+3) ≤ χf(C2n+1).
- For n ≥8, the fractional chromatic number satisfies χf(C2n+1) < 4.99.The bound follows from a computer search for the 17-vertex case together with monotonicity.
- The integer chromatic number is also monotone decreasing, and for n ≥3 it lies between 5 and 7.
- The limiting value of χ(C2n+1) exists but remains unknown among 5, 6, and 7.
A.3 Fractional chromatic number upper bounds for C Cn
Computer searches produce upper bounds on fractional chromatic numbers for confusion graphs of complements of odd cycles, suggesting monotone behavior without guaranteeing tightness.
- Computer searches for large independent sets provide upper bounds on the fractional chromatic numbers of these confusion graphs.Because the graphs are Cayley graphs, the search targets large independent sets; the resulting bounds need not be optimal.
- The computed bounds suggest that the fractional chromatic numbers decrease monotonically across the odd-cycle family.
A.4 Coloring the confusion graph of C7 with 7 colors
The section presents a computer-found legal coloring of the confusion graph associated with C7 using seven colors and provides a verification program.
- A legal coloring using 7 colors is given for the confusion graph associated with C7.The coloring was found using a computer program.
- The table represents the graph’s 128 vertices, with each vertex identified by the sum of its row and column indices.The highlighted example is vertex 16 + 4, assigned to the seventh color.
- A computer program is available to verify that the displayed coloring is legal.