Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-128 | 13th August 2016 18:23

Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover


Authors: Irit Dinur
Publication: 13th August 2016 18:23
Downloads: 2229


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

ISSN 1433-8092 | Imprint