Computational Complexity of Interference Alignment for Symmetric MIMO Networks

It is known that the problem of maximizing the sum degrees of freedom (DoF) for an arbitrary MIMO network without symbol extension is NP-hard in the number of transmitter-receiver pairs. The DoF achievability problem is also NP-hard if each transmitter/receiver has at least three antennas, and is polynomial-time solvable if each transmitter/receiver has no more than two antennas. It was conjectured that for the special case of the symmetric network (where all the transmitters have the same number of antennas and all the receivers have the same number of antennas), polynomial-time algorithms might exist for these two problems. In this paper, we show that the conjecture holds only in a very limited sense. We also show that for two important special cases of the symmetric network, both problems are polynomial-time solvable if the number of antennas at each transmitter/receiver is no more than two, and generally are NP-hard otherwise.