The label-cover problem was introduced in cite{ABSS} and shown there to be quasi-NP-hard to approximate to within a factor of 2log1?n for any {em constant} 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 2log1?n where =1loglogcn for any constant c12 . 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.
展开▼
