Interactive Function Computation

We investigate the role of interaction for computa- tion problem settings where nodes intend to compute functions of the raw messages generated at other nodes. In this work, we make some progress on a more elementary research component: feedback. Specifically we characterize the feedback computing capacity of a two-transmitter two-receiver linear determinis- tic network in which both receivers wish to decode a linear function (modulo-2 sum) of Bernoulli sources generated at the transmitters. Inspired by the concept of interference alignment and compute-and-forward, we develop a new achievable scheme called interactive function alignment. A new converse theorem is established that is tighter than cut-set based and genie-aided bounds. As a consequence of this result, we show that interaction can provide an arbitrarily large gain for computation, as in classical communication settings.

Published in:
Proceedings of the 2013 IEEE International Symposium on Information Theory, 2329-2333
Presented at:
2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, July 7-12, 2013

 Record created 2013-07-17, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)