Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-112 | 10th August 2011 15:09

The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover


Authors: Dana Moshkovitz
Publication: 10th August 2011 16:04
Downloads: 1966


In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the conjecture. We pursue this line of research by establishing a tight NP-hardness result for the Set-Cover problem. Specifically, we show that under the projection games conjecture (in fact, under a quantitative version of the conjecture that is only slightly beyond the reach of current techniques), it is NP-hard to approximate Set-Cover on instances of size N to within $(1-x)ln N$ for arbitrarily small $x>0$. We do this by modifying Feige's reduction that gives a $(1-x)ln N$ inapproximability under the assumption that $NP$ is not contained in $DTIME(N^{O(\log\log N)})$.

ISSN 1433-8092 | Imprint