A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
<|reference_start|>A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover: 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-\epsilon)$ for any $k \geq 3$ and any $\epsilon>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.<|reference_end|>
@article{dinur2003a,
    title={A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover},
    author={Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev},
    journal={arXiv preprint arXiv:cs/0304026},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304026},
    primaryClass={cs.CC}
}