On Distributed Computing for Functions With Certain Structures
From MaRDI portal
Abstract: The problem of distributed function computation is studied, where functions to be computed is not necessarily symbol-wise. A new method to derive a converse bound for distributed computing is proposed; from the structure of functions to be computed, information that is inevitably conveyed to the decoder is identified, and the bound is derived in terms of the optimal rate needed to send that information. The class of informative functions is introduced, and, for the class of smooth sources, the optimal rate for computing those functions is characterized. Furthermore, for i.i.d. sources with joint distribution that may not be full support, functions that are composition of symbol-wise function and the type of a sequence are considered, and the optimal rate for computing those functions is characterized in terms of the hypergraph entropy. As a byproduct, our method also provides a conceptually simple proof of the known fact that computing a Boolean function may require as large rate as reproducing the entire source.
Cited in
(7)- Fair distributed computation of reactive functions
- scientific article; zbMATH DE number 5972643 (Why is no real title available?)
- Fast Distributed Algorithms for Computing Separable Functions
- scientific article; zbMATH DE number 1254029 (Why is no real title available?)
- On Distributed Computations with Limited Resources
- Distributed Point Functions and Their Applications
- Function-correcting codes with homogeneous distance
This page was built for publication: On Distributed Computing for Functions With Certain Structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566540)
