On the Generic Capacity of K-User Symmetric Linear Computation Broadcast
Yuhang Yao, Syed A. Jafar · IEEE Transactions on Information Theory · 2024
Linear computation broadcast (LCBC) refers to a setting withddimensional data stored at a central server, whereKusers, 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 ad-dimensional vector with elements in a finite field Fpnwherepnis 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 toK= 3 users. Since LCBC includes index coding as a special case, largeKsettings 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 (allcases), by focusing on thegenericsetting (almost allcases) this work shows that the generic capacity of the symmetric LCBC (where every user hasm’ dimensions of side-information andmdimensions of demand) for large number of users (K≥dsuffices) isCg= 1/Δg, where Δg= min { max{0,d-m′},dm/m+m′}, is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for largen, among all LCBC instances with the given parametersp,K,d,m,m′. Relative to baseline schemes of random coding or separate transmissions,Cgshows an extremal gain by a factor ofKas a function of number of users, and by a factor of ≈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.