Skip to main content
Article
Zero-Error Function Computation on a Directed Acyclic Network
2018 IEEE Information Theory Workshop, ITW 2018
  • Ardhendu S. Tripathy, Missouri University of Science and Technology
  • Aditya Ramamoorthy
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.

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
1-15-2019
Publication Date
15 Jan 2019
Disciplines
Citation Information
Ardhendu S. Tripathy and Aditya Ramamoorthy. "Zero-Error Function Computation on a Directed Acyclic Network" 2018 IEEE Information Theory Workshop, ITW 2018 (2019)
Available at: http://works.bepress.com/ardhendu-s-tripathy/8/