Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
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. © 1963-2012 IEEE.
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Eric Price, David P. Woodruff
FOCS 2011