Distributed computing of functions of structured sources with helper side information

Malak, Derya
SPAWC 2023, 24th IEEE International Workshop on Signal Processing Advances in Wireless Communications,
25-28 September 2023, Shanghai, China

In this work, we consider the problem of distributed computing of functions of structured sources, focusing on the classical setting of two correlated sources and one user that seeks
the outcome of the function while benefiting from low-rate side information provided by a helper node. Focusing on the case where the sources are jointly distributed according to a very general mixture model, we here provide an achievable coding scheme that manages to substantially reduce the communication cost of distributed computing by exploiting the nature of the joint distribution of the sources, the side information, as well as by exploiting the symmetry enjoyed by the desired functions. Our scheme — which can readily apply in a variety of real-life scenarios including learning, combinatorics, and graph neural network applications — is here shown to provide substantial reductions in the communication costs, while simultaneously providing computational savings by reducing the exponential complexity of joint decoding techniques to a complexity that is
merely linear.

Communication systems
Eurecom Ref:
© 2023 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
See also:

PERMALINK : https://www.eurecom.fr/publication/7366