Network decomposition for function computation
Changho Suh, Michael Gastpar · 2013
We develop a network-decomposition framework to provide elementary parallel subnetworks that can constitute an original network without loss of optimality. In our earlier work, a network decomposition is constructed for the Avestimehr-Diggavi-Tse deterministic network which well captures key properties of wireless Gaussian networks. In this work, we apply this decomposition framework to general problem settings where receivers intend to compute functions of the messages generated at transmitters. Depending on functions, these settings include a variety of network problems, ranging from classical communication problems (such as multiple-unicast and multicast problems) to function computation problems. For many of these problems, we show that coding separately over the decomposed orthogonal subnetworks provides optimal performances, thus establishing a separation principle.