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.