Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KAI ZHE ZHENG:
All reports by Author Kai Zhe Zheng:

TR24-027 | 18th February 2024
Dor Minzer, Kai Zhe Zheng

Near Optimal Alphabet-Soundness Tradeoff PCPs

We show that for all $\varepsilon>0$, for sufficiently large prime power $q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs ... more >>>




ISSN 1433-8092 | Imprint