Deterministic-Coding Capacity of Networks in the Low-Power Regime

The deterministic-coding capacity of a network is the capacity of a network when nodes are restricted to transmitting reliable information, that is, (asymptotically) deterministic functions of the source messages. This is a generalization of network coding to wireless networks. The main contribution of this paper is to develop new outer bounds on the deterministic-coding capacity in the low-power regime, SNR → 0. This is accomplished by developing a technique for finding the limits of single letter bounds for SNR → 0 even when these cannot be evaluated for finite SNR. It is shown that these outer bounds are tight in a number of cases, including the butterfly network of Ahlswede et al. in a wireless setting.