Capacity region of the linear deterministic broadcast channel with a diamond message set

At least 5 years old · documented by

Let KK be the number of receivers, let E={Mϕ‾,MK‾,MK−1‾,MK−1.K‾}\mathsf{E}=\{M_{\overline{\phi}},M_{\overline{K}},M_{\overline{K-1}},M_{\overline{K-1.K}}\} be the diamond message set, and let rSr_S denote the rank associated with a receiver-index set S=l1l2⋯lN⊆[1:K]S=l_1l_2\cdots l_N\subseteq [1:K]:

rS=rank⁡([Hl1⋮HlN]).r_S=\operatorname{rank}\left(\begin{bmatrix}\boldsymbol{H}_{l_1}\\ \vdots \\ \boldsymbol{H}_{l_N}\end{bmatrix}\right).

The message rates are Rϕ‾,RK‾,RK−1‾,RK−1.K‾R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1}},R_{\overline{K-1.K}}.

The capacity-region claim. The capacity region of the KK-user linear deterministic broadcast channel for this diamond message set is the set of non-negative rate tuples satisfying, for every j∈{1,2,⋯ ,K−2}j\in\{1,2,\cdots,K-2\},

Rϕ‾+RK−1‾≤rK,R_{\overline{\phi}}+R_{\overline{K-1}}\leq r_K, Rϕ‾+RK‾≤rK−1,R_{\overline{\phi}}+R_{\overline{K}}\leq r_{K-1}, Rϕ‾+RK−1‾+RK‾≤rK−1.K,R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq r_{K-1.K}, Rϕ‾+RK−1‾+RK‾+RK−1.K‾≤rj,R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq r_j, 2Rϕ‾+RK−1‾+RK‾+RK−1.K‾≤rj.K−1.K−rK−1.K+rK−1+rK,2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq r_{j.K-1.K}-r_{K-1.K}+r_{K-1}+r_K, 2Rϕ‾+2RK−1‾+2RK‾+RK−1.K‾≤rj.K−1+rj.K+rK−1.K−rj.K−1.K.2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq r_{j.K-1}+r_{j.K}+r_{K-1.K}-r_{j.K-1.K}.

The claim gives an exact characterization of the achievable rates for this deterministic broadcast-channel message configuration; the supplied text does not indicate whether the result is intended as a conjecture or has an independently established resolution.

References

Primary source

Mohamed Salman and Mahesh K. Varanasi, “Diamond Message Set Groupcasting: From an Inner Bound for the DM Broadcast Channel to the Capacity Region of the Combination Network”, arXiv:2011.04760 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.