A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
| dc.creator | Dinur, Irit | |
| dc.creator | Guruswami, Venkatesan | |
| dc.creator | Khot, Subhash | |
| dc.creator | Regev, Oded | |
| dc.date | 2003-04-19 | |
| dc.date.accessioned | 2026-07-07T03:19:36Z | |
| dc.date.available | 2026-07-07T03:19:36Z | |
| dc.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. | |
| dc.identifier | https://arxiv.org/abs/cs/0304026 | |
| dc.identifier | http://arxiv.org/abs/cs/0304026 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31528 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover | |
| dc.type | text |