Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer, Kai Zhe Zheng

We show that for all $\epsilon >0$, for sufficiently large $q\in \mathbb{N}$ power of $2$, for all $\delta >0$, it is NP-hard to distinguish whether a given $2$-Prover-$1$-Round project…