Mildly exponential reduction from gap 3SAT to polynomial gap label cover
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 a 0 any algorithm for na approximating the value of label cover must run in time at least nO(exp(1/a) where n is the size of the instance. Put differently, if there is a polynomial time algorithm for approximating the value of label cover to within a factor of approximation of no(1) then gap 3SAT (and thus, random 3SAT) must have faster than exponential time algorithms. Our proof is a twist on the well studied parallel repetition reduction from 3SAT to label cover. Our key observation is that if we take unordered repetition, replacing tuples by sets, then we can afford to take the number of repetitions to be linear in n, and generate an instance of size exp(n) which results in the claimed parameters.
Electron. Colloquium Comput. Complex.