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:
No takes yet. Share an insight, caveat, or question.
Minzer et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: