English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the well-known Label Cover problem under the additional requirementthat 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 allconstant $\epsilon > 0$. A similar theorem was claimed by Elkin and Peleg[ICALP 2000], but their proof was later found to have a fundamental error. Weuse 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 forwhich super-logarithmic hardness was not known. Assuming $NP \not\subseteqBPTIME(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 afactor better than $2^{(\log^{1-\epsilon} n) / k}$ (for large enough $n$). Asimilar hardness for basic $k$-spanner was claimed by Elkin and Peleg [ICALP2000], but the error in their analysis of Label Cover made this proof fail aswell. Thus for the problem of Label Cover with large girth we give the firstnon-trivial lower bound. For the basic $k$-spanner problem we improve theprevious best lower bound of $\Omega(\log n)/k$ by Kortsarz [Algorithmica1998]. Our main technique is subsampling the edges of 2-query PCPs, whichallows us to reduce the degree of a PCP to be essentially equal to thesoundness desired. This turns out to be enough to essentially guarantee largegirth.

Label Cover instances with large girth and the hardness of approximating basic k-spanner