Prof. Michael Elkin

We show that the radio broadcast problem is Ω(log n)-inapproximable unless NP ⊆ BPTIME(n O(log log n)). This is the first result on the hardness of approximation of this problem. Our reduction is based on the reduction from the Label-Cover problem to the Set Cover problem due to Lund and Yannakakis [LY94], and uses some new ideas.