Skip to main content
Presentation
On computation rates for arithmetic sum
2016 IEEE International Symposium on Information Theory (ISIT)
  • Ardhendu Tripathy, Iowa State University
  • Aditya Ramamoorthy, Iowa State University
Document Type
Conference Proceeding
Conference
2016 IEEE International Symposium on Information Theory (ISIT)
Publication Version
Accepted Manuscript
Link to Published Version
http://dx.doi.org/10.1109/ISIT.2016.7541720
Publication Date
1-1-2016
DOI
10.1109/ISIT.2016.7541720
Conference Title
2016 IEEE International Symposium on Information Theory (ISIT)
Conference Date
July 10–15, 2016
Geolocation
(41.3850639, 2.1734034999999494)
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.
Comments

This proceeding is from 2016 IEEE International Symposium on Information Theory, Barcelona, 2016, pp. 2354-2358. doi:10.1109/ISIT.2016.7541720. Posted with permission.

Rights
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Language
en
File Format
application/pdf
Citation Information
Ardhendu Tripathy and Aditya Ramamoorthy. "On computation rates for arithmetic sum" Barcelona, Spain2016 IEEE International Symposium on Information Theory (ISIT) (2016) p. 2354 - 2358
Available at: http://works.bepress.com/ardhendu-tripathy/1/