CATS-Apr-18-2014
Title[edit]
Label Cover Instances with Large Girth and the Hardness of Approximating Spanners
Speaker[edit]
Michael Dinitz, Johns Hopkins University
Abstract[edit]
We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is at least k, the problem is roughly 2^{\log^{1-\epsilon} n/k} hard to approximate for all constant \epsilon > 0, which is the first non-trivial lower bound. Our main technique is subsampling the edges of 2-query PCPs, which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth, as well as giving an almost tight tradeoff between the degree and the soundness.
We use the new proof to show inapproximability for the basic k-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP \not\subseteq BPTIME(2^{polylog(n)}), we show (roughly) that for every k \geq 3 and every constant \epsilon > 0 it is hard to approximate the basic k-spanner problem within a factor better than 2^{(\log^{1-\epsilon} n) / k}. Time permitting, we will also show an additional hardness result for the Lowest Degree k-Spanner problem.
Join work with Guy Kortsarz and Ran Raz.
