Improved Multilayered PCPs and Hypergraph Vertex Cover

Abstract

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and another one with $2$-to-$2$ constraints. Using these constructions we obtain the following results for the hypergraph vertex cover problem: $\bullet$ For $k=3$, for all $\epsilon >0$, approximating the minimum vertex cover of a given $3$-uniform hypergraph within factor $1+\sqrt{2}-\epsilon$ is NP-hard. Previously, the best known result due to [Dinur, Guruswami, Khot, Regev, SICOMP 2005] achieved a factor of $2-\epsilon$. $\bullet$ For $k\ge 4$, for all $\epsilon >0$, approximating the minimum vertex cover of a given $k$-uniform hypergraph within factor $k-\epsilon$ is NP-hard, which is tight. Previous works established this result assuming the Unique-Games Conjecture [Khot, Regev, JCSS 2008], and a weaker factor of $k-1-\epsilon$ for standard NP-hardness [Dinur, Guruswami, Khot, Regev, SICOMP 2005]. $\bullet$ Assuming the Exponential Time Hypothesis, for all $k\ge 3$ and $\epsilon >0$ there is $C>0$ such that no $2^{n/{\log }^{C}n}$-time algorithm approximates the minimum vertex cover in a $k$-uniform, $n$-vertex hypergraph within factor $k-1-\epsilon$. The proofs were obtained using ChatGPT 5.6 Pro and subsequently rewritten by the communicators.