ECCC-Report TR16-128https://eccc.weizmann.ac.il/report/2016/128Comments and Revisions published for TR16-128en-usSat, 13 Aug 2016 18:23:50 +0300
Paper TR16-128
| Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover |
Irit Dinur
https://eccc.weizmann.ac.il/report/2016/128We 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, if there is a polynomial time algorithm for approximating the value of label cover to within a factor of approximation of $n^{o(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.Sat, 13 Aug 2016 18:23:50 +0300https://eccc.weizmann.ac.il/report/2016/128