Zero-Error Function Computation on a Directed Acyclic Network
Abstract
We study the rate region of variable-length source-network codes that are used to compute a function of messages observed over a network. The particular network considered here is the simplest instance of a directed acyclic graph (DAG) that is not a tree. Existing work on zero-error function computation in DAG networks provides bounds on the computation capacity, which is a measure of the amount of communication required per edge in the worst case. This work focuses on the average case: an achievable rate tuple describes the expected amount of communication required on each edge, where the expectation is over the probability mass function of the source messages. We describe a systematic procedure to obtain outer bounds to the rate region for computing an arbitrary demand function at the terminal. Our bounding technique works by lower bounding the entropy of the descriptions observed by the terminal conditioned on the function value and by utilizing the Schur-concave property of the entropy function.
Recommended Citation
A. S. Tripathy and A. Ramamoorthy, "Zero-Error Function Computation on a Directed Acyclic Network," 2018 IEEE Information Theory Workshop, ITW 2018, Institute of Electrical and Electronics Engineers (IEEE), Jan 2019.
The definitive version is available at https://doi.org/10.1109/ITW.2018.8613467
Meeting Name
2018 IEEE Information Theory Workshop, ITW 2018 (2018: Nov. 25-29, Guangzhou, China)
Department(s)
Computer Science
International Standard Book Number (ISBN)
978-153863599-5
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
15 Jan 2019
