On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes

Karthik C. S., Inbal Livni-Navon

In the $(k,h)$-SetCover problem, we are given a collection $\mathcal{S}$ of sets over a universe $U$, and the goal is to distinguish between the case that $\mathcal{S}$ contains $k…