A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.
- Characteristic,
- Function Computation,
- Incidence Structures,
- Network Coding,
- Sum-Networks
Available at: http://works.bepress.com/ardhendu-s-tripathy/15/
This work was supported by the National Science Foundation under Grant CCF-1149860, Grant CCF-1320416, Grant CCF-1718470, and Grant DMS-1120597.
This paper was presented in part at the 2014 52nd Allerton Conference on Communication, Control, and Computing and the 2015 IEEE International Symposium on Information Theory.