Near Optimal Alphabet-Soundness Tradeoff PCPs

We show that for all є>0, for sufficiently large prime power q, for all δ>0, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/q^(1-є). This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q, improving upon a result of [Chan 2016]. Our result has the following implications: