Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Label Cover instances with large girth and the hardness of approximating
  basic k-spanner   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 some $k$,
the problem is roughly $2^{\log^{1-\epsilon} n/k}$ hard to approximate for all
constant $\epsilon > 0$. A similar theorem was claimed by Elkin and Peleg
[ICALP 2000], but their proof was later found to have a fundamental error. 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 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}$ (for large enough $n$). A
similar hardness for basic $k$-spanner was claimed by Elkin and Peleg [ICALP
2000], but the error in their analysis of Label Cover made this proof fail as
well. Thus for the problem of Label Cover with large girth we give the first
non-trivial lower bound. For the basic $k$-spanner problem we improve the
previous best lower bound of $\Omega(\log n)/k$ by Kortsarz [Algorithmica
1998]. 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 essentially guarantee large
girth.

19
The categories of this paper are: eess
10
The categories of this paper are: q-bio
24
The categories of this paper are: dg-ga
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
27
The categories of this paper are: comp-gas
7
The categories of this paper are: hep-th
17
The categories of this paper are: q-fin
23
The categories of this paper are: solv-int
20
The categories of this paper are: acc-phys
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
9
The categories of this paper are: nlin
4
The categories of this paper are: cond-mat