|| Topological Interference Management with Adversarial Perturbation
||Ya-Chun Liang, Chung-Shou Liao, National Tsing Hua University, Taiwan; Xinping Yi, University of Liverpool, United Kingdom|
||Monday, 19 July, 22:40 - 23:00
||Monday, 19 July, 23:00 - 23:20
In this paper, we consider the topological interference management (TIM) problem in a dynamic setting, where an adversary perturbs network topology to prevent the exploitation of sophisticated coding opportunities (e.g., interference alignment). Focusing on a special class of network topology - chordal networks - we investigate algorithmic aspects of the TIM problem under adversarial topology perturbation. In particular, given the adversarial perturbation with respect to edge insertion/deletion, we propose a dynamic graph coloring algorithm that allows for a constant number of re-coloring updates against each inserted/deleted edge to achieve the information-theoretic optimality. This is a sharp reduction of the general graph re-coloring, whose optimal number of updates scales as the size of the network, thanks to the delicate exploitation of the structural properties of weakly chordal graphs.