Title: Topological Interference Management with Decoded Message Passing,
Abstract: The topological interference management (TIM) problem studies
partially-connected interference networks with no channel state information
except for the network topology (i.e., connectivity graph) at the transmitters.
In this paper, we consider a similar problem in the uplink cellular networks,
while message passing is enabled at the receivers (e.g., base stations), so
that the decoded messages can be routed to other receivers via backhaul links
to help further improve network performance. For this TIM problem with decoded
message passing (TIM-MP), we model the interference pattern by conflict
digraphs, connect orthogonal access to the acyclic set coloring on conflict
digraphs, and show that one-to-one interference alignment boils down to
orthogonal access because of message passing. With the aid of polyhedral
combinatorics, we identify the structural properties of certain classes of
network topologies where orthogonal access achieves the optimal
degrees-of-freedom (DoF) region in the information-theoretic sense. The
relation to the conventional index coding with simultaneous decoding is also
investigated by formulating a generalized index coding problem with successive
decoding as a result of decoded message passing. The properties of reducibility
and criticality are also studied, by which we are able to prove the linear
optimality of orthogonal access in terms of symmetric DoF for the networks up
to four users with all possible network topologies (218 instances). Practical
issues of the tradeoff between the overhead of message passing and the
achievable symmetric DoF are also discussed, in the hope of facilitating
efficient backhaul utilization.