A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Authors

Dinur, Irit

Guruswami, Venkatesan

Khot, Subhash

Regev, Oded

Description

Given a $k$-uniform hyper-graph, the E$k$-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 E$k$-Vertex-Cover is NP-hard to approximate within factor $(k-1-ε)$ for any $k \geq 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.