A generalized cut-set bound for deterministic multi-flow networks and its applications
Ilan Shomorony, A. Salman Avestimehr · 2014
We present a new outer bound for the sum capacity of general multi-unicast deterministic networks. Intuitively, this bound can be understood as applying the cut-set bound to concatenated copies of the original network with a special restriction on the allowed transmit signal distributions. We first study applications to finite-field networks, where we obtain a general outer-bound expression in terms of ranks of the transfer matrices. We then show that, even though our outer bound is for deterministic networks, a result from [1] relating the capacity of AWGN K×K×K networks and the capacity of a deterministic counterpart allows us to establish an outer bound to the DoF of K×K×K wireless networks with general connectivity. This bound is tight in the case of the “adjacent-cell interference” topology, and yields graph-theoretic necessary and sufficient conditions for K DoF to be achievable in general topologies.