__
TR99-015 | 25th April 1999 00:00
__

#### On the hardness of approximating label cover

**Abstract:**
The label-cover problem was introduced in \cite{ABSS} and shown

there to be quasi-NP-hard to approximate to within a factor of

$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This

combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}

for showing hardness-of-approximation of numerous problems. We

present a direct combinatorial reduction from low

error-probability PCP \cite{DFKRS} to label-cover. This

improves on \cite{ABSS} in two ways. First, it improves the

previous hardness-of-approximation factor known for label-cover,

achieving a factor of $2^{\log^{1-\delta}n}$ where

$\delta=1/\log\log^c n$ for any constant $c<1/2$. Furthermore, we

show approximating label-cover is NP-hard for these large

factors, compared to the {\em quasi} NP-hardness, obtained

previously.

Our result for label-cover immediately strengthens the known

hardness result for several approximation problems as mentioned

above, for example the Minimum-Monotone-Satisfying-Assignment

(MinMonSAT) problem \cite{ABMP}. Furthermore, we examine a hierarchy

of approximation problems obtained by restricting the depth of the

monotone formula in MinMonSAT. This hierarchy turns out to be

equivalent to an AND/OR scheduling hierarchy suggested in

\cite{GM}. We show some hardness results for certain levels in this

hierarchy, and place label-cover between levels 3 and 4. This

partially answers an open problem from \cite{GM} regarding the

precise complexity of each level in the hierarchy, and the place of

label-cover in it.