EUVIMEDEUVIMED entdecken
Crossref

On the Generic Capacity of K -User Symmetric Linear Computation Broadcast

Yuhang Yao, Syed A. Jafar

IEEE Transactions on Information Theory · 2024-05 · 70 (5) · 3693-3717

DOI: 10.1109/tit.2024.3382257 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2024-05. Verfasst von Yuhang Yao und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 61 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations, Office of Naval Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Linear computation broadcast (LCBC) refers to a setting with d dimensional data stored at a central server, where K users, each with some prior linear side-information, wish to compute various linear combinations of the data. For each computation instance, the data is represented as a d-dimensional vector with elements in a finite field $\mathbb {F}_{p^{n}}$ where $p^{n}$ is a power of a prime. The computation is to be performed many times, and the goal is to determine the minimum amount of information per computation instance that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost per computation instance is the capacity of LCBC. The capacity is known for up to $K=3$ users. Since LCBC includes index coding as a special case, large K settings of LCBC are at least as hard as the index coding problem. As such the general LCBC problem is beyond our reach and we do not pursue it. Instead of the general setting (all cases), by focusing on the generic setting (almost all cases) this work shows that the generic capacity of the symmetric LCBC (where every user has $m'$ dimensions of side-information and m dimensions of demand) for large number of users ( $K \geq d$ suffices) is $C_{g}=1/\Delta _{g}$ , where $\Delta _{g}=\min \left \{{\max \{0,d-m'\}, \frac {dm}{m+m'}}\right \}$ , is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for large n, among all LCBC instances with the given parameters $p,K,d,m,m'$ . Relative to baseline schemes of random coding or separate transmissions, $C_{g}$ shows an extremal gain by a factor of K as a function of number of users, and by a factor of $\approx d/4$ as a function of data dimensions, when optimized over remaining parameters. For arbitrary number of users, the generic capacity of the symmetric LCBC is characterized within a factor of 2.

Förderung

  • Division of Computing and Communication Foundations
  • Office of Naval Research

Zitieren

APA

Yao, Y., & Jafar, S. A. (2024). On the Generic Capacity of K -User Symmetric Linear Computation Broadcast. IEEE Transactions on Information Theory, 70(5), 3693-3717. https://doi.org/10.1109/tit.2024.3382257

Vancouver

Yao Y, Jafar SA. On the Generic Capacity of K -User Symmetric Linear Computation Broadcast. IEEE Transactions on Information Theory. 2024;70(5):3693-3717. doi:10.1109/tit.2024.3382257

BibTeX
@article{Yao2024,
  author = {Yao, Yuhang and Jafar, Syed A.},
  title = {On the Generic Capacity of K -User Symmetric Linear Computation Broadcast},
  journal = {IEEE Transactions on Information Theory},
  year = {2024},
  volume = {70},
  number = {5},
  pages = {3693--3717},
  doi = {10.1109/tit.2024.3382257}
}
Kostenlos starten →