### 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 language | English (US) |
---|---|

Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

Pages | 595-601 |

Number of pages | 7 |

State | Published - 2003 |

Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |

### Other

Other | 35th Annual ACM Symposium on Theory of Computing |
---|---|

Country | United States |

City | San Diego, CA |

Period | 6/9/03 → 6/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)