Computing Linear Functions by Linear Coding Over Networks

By Rathinakumar Appuswamy, Massimo Franceschetti. 2011

51 citations recorded by the source corpus.

We consider the scenario in which a set of sources generates messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Hariharan Rahul
2. Omid Salehi-Abari
3. Dina Katabi
4. Sachin Rajsekhar Katti
5. Kaibin Huang
6. Guangxu Zhu

In Electrical and Electronic Engineering

1. Hariharan Rahul
2. Omid Salehi-Abari
3. Dina Katabi
4. Kaibin Huang
5. Guangxu Zhu
6. Fadel M. Adib

Citations in the corpus

• Over-the-air Function Computation in Sensor Networks (2016, background): “Function Computation: There has been a lot of recent interest in distributed function computation from the information theory community [10, 28, 3, 22, 11].”