Finding Three Transmissions is Hard

Download Now Date Added: Nov 2012
Format: PDF

The authors investigate a fundamental wireless broadcast problem called Index coding. They focus on binary linear scalar index coding problems when it is a-priori known that the optimal solution requires three transmissions. For this case, they characterize the relation of the clique cover number of the side information graph G and the optimal index code. This allows them to show that even when there is a-priori knowledge that three transmissions can solve a given index coding problem, ending these transmissions is NP-hard. Another implication of their results is that for three solvable undirected problems, the benefit of interference alignment solutions is at most one compared to a simple clique cover.