Irit Dinur, S. Safra

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 ...
more >>>

Irit Dinur

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>