A new multilayered PCP and the hardness of hypergraph vertex cover

Irit Dinur, Subhash Khot, Venkatesan Guruswami, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k -1 - ε) for any k ≥ 3 and any ε > 0. The result is essentially tight as this problem can be easily approximated within factor k. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages595-601
Number of pages7
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Other

Other35th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/9/036/11/03

Keywords

  • Hardness of Approximation
  • Hypergraph Vertex Cover
  • Long Code
  • Multilayered PCP

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A new multilayered PCP and the hardness of hypergraph vertex cover'. Together they form a unique fingerprint.

  • Cite this

    Dinur, I., Khot, S., Guruswami, V., & Regev, O. (2003). A new multilayered PCP and the hardness of hypergraph vertex cover. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 595-601)