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.
Record created on 2013-07-17, modified on 2016-08-09