### Abstract

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^{(log1-εn)/k} hard to approximate for all constant ε > 0. A similar theorem was claimed by Elkin and Peleg [ICALP 2000] as part of an attempt to prove hardness for the basic k-spanner problem, but their proof was later found to have a fundamental error. Thus we give both the first non-trivial lower bound for the problem of Label Cover with large girth as well as the first full proof of strong hardness 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 ⊈ BPTIME(2^{polylog(n)}), we show (roughly) that for every k ≥ 3 and every constant ε > 0 it is hard to approximate the basic k-spanner problem within a factor better than 2 ^{(log1-εn)/k}. This improves over the previous best lower bound of only Ω(logn)/k from [17]. 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.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings |

Pages | 290-301 |

Number of pages | 12 |

Edition | PART 1 |

DOIs | |

State | Published - Dec 1 2012 |

Externally published | Yes |

Event | 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom Duration: Jul 9 2012 → Jul 13 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | PART 1 |

Volume | 7391 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 |
---|---|

Country | United Kingdom |

City | Warwick |

Period | 7/9/12 → 7/13/12 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Label cover instances with large girth and the hardness of approximating basic k-spanner'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings*(PART 1 ed., pp. 290-301). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7391 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-31594-7_25