Revised: July 22, 2014

Published: June 9, 2015

**Keywords:**set-cover, PCP, Sliding Scale Conjecture, Projection Games Conjecture

**Categories:**complexity theory, algorithms, approximation algorithms, inapproximability, set-cover, PCP, Sliding Scale Conjecture, label cover, Projection Games Conjecture, special issue, APPROX, APPROX-RANDOM 2012 special issue, short

**ACM Classification:**F.2.2, G.1.6

**AMS Classification:**68W25

**Abstract:**
[Plain Text Version]

We establish a tight $\NP$-hardness result for approximating the SET-COVER problem based on a strong PCP theorem. Our work implies that it is $\NP$-hard to approximate SET-COVER on instances of size $N$ to within $(1-\alpha)\ln N$ for arbitrarily small $\alpha>0$. Our reduction establishes a tight trade-off between the approximation accuracy $\alpha$ and the running time $\exp(N^{\Omega(\alpha)})$ assuming SAT requires exponential time.

The reduction is obtained by modifying Feige's reduction. The latter provides a lower bound of $\exp(N^{\Omega(\alpha/\log\log N)})$ on the time required for $(1-\alpha)\ln N$-approximating SET-COVER assuming SAT requires exponential time. The modification uses a combinatorial construction of a bipartite graph in which any coloring of the first side that does not use a color for more than a small fraction of the vertices, makes most vertices on the other side have all their neighbors colored in different colors.

In the conference version of this paper, the SET-COVER result was conditioned on a conjecture we call “The Projection Games Conjecture” (PGC), a strengthening of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games LABEL-COVER. More precisely, the prerequisite was a quantitative version of this conjecture that was slightly beyond what was known at the time of the paper's writing. Shortly afterward, Dinur and Steurer, based on a result by the author and Raz, proved the quantitative version of the conjecture sufficient for the SET-COVER result. More broadly, in this paper we discuss the Projection Games Conjecture and its applications to hardness of approximation, e.g., to polynomial hardness factors for the CLOSEST-VECTOR problem and to studying the behavior of CSPs around their approximability threshold.

A preliminary version of this paper appeared in the Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012).