Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SLIDING SCALE:
Reports tagged with sliding scale:
TR16-128 | 13th August 2016
Irit Dinur

#### 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 $\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 >>>

ISSN 1433-8092 | Imprint