Skip to main content
Article
On Computation Rates for Arithmetic Sum
IEEE International Symposium on Information Theory - Proceedings
  • Ardhendu S. Tripathy, Missouri University of Science and Technology
  • Aditya Ramamoorthy
Abstract

For zero-error function computation over directed acyclic networks, existing upper and lower bounds on the computation capacity are known to be loose. In this work we consider the problem of computing the arithmetic sum over a specific directed acyclic network that is not a tree. We assume the sources to be i.i.d. Bernoulli with parameter 1/2. Even in this simple setting, we demonstrate that upper bounding the computation rate is quite nontrivial. In particular, it requires us to consider variable length network codes and relate the upper bound to equivalently lower bounding the entropy of descriptions observed by the terminal conditioned on the function value. This lower bound is obtained by further lower bounding the entropy of a so-called clumpy distribution. We also demonstrate an achievable scheme that uses variable length network codes and in-network compression.

Meeting Name
2016 IEEE International Symposium on Information Theory, ISIT (2016: Jul. 10-15, Barcelona, Spain)
Department(s)
Computer Science
Comments
This work was supported in part by the National Science Foundation by grants CCF- 1320416, CCF- 1149860 and DMS-1120597.
International Standard Book Number (ISBN)
978-150901806-2
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
8-10-2016
Publication Date
10 Aug 2016
Disciplines
Citation Information
Ardhendu S. Tripathy and Aditya Ramamoorthy. "On Computation Rates for Arithmetic Sum" IEEE International Symposium on Information Theory - Proceedings (2016) p. 2354 - 2358 ISSN: 2157-8095
Available at: http://works.bepress.com/ardhendu-s-tripathy/12/