A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Irit Dinur, Venkatesan Guruswami, Subhash Khot +1

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 constr…