On Computation Rates for Arithmetic Sum

Thumbnail Image
Date
2016-01-01
Authors
Tripathy, Ardhendu
Ramamoorthy, Aditya
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Tripathy, Ardhendu
Assistant Professor
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Electrical and Computer Engineering
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 \textit{clumpy distribution}. We also demonstrate an achievable scheme that uses variable length network codes and in-network compression.

Comments

This preprint is from arXiv:1601.07228 [cs.IT]. Posted with permission.

Description
Keywords
Citation
DOI
Source
Copyright
Fri Jan 01 00:00:00 UTC 2016
Collections