| Paper ID | D6-S3-T1.2 |
| Paper Title |
Topological Interference Management with Adversarial Perturbation |
| Authors |
Ya-Chun Liang, Chung-Shou Liao, National Tsing Hua University, Taiwan; Xinping Yi, University of Liverpool, United Kingdom |
| Session |
D6-S3-T1: Interference |
| Chaired Session: |
Monday, 19 July, 22:40 - 23:00 |
| Engagement Session: |
Monday, 19 July, 23:00 - 23:20 |
| Abstract |
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.
|
