Interactive function computation

We investigate the role of interaction for computation 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 deterministic 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.