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: 1) Near optimal hardness for Quadratic Programming: it is NP-hard to approximate the value of a given Boolean Quadratic Program within factor (log n)(1 - o(1)) under quasi-polynomial time reductions. This result improves a result of [Khot-Safra 2013] and nearly matches the performance of the best known approximation algorithm [Megrestki 2001, Nemirovski-Roos-Terlaky 1999 Charikar-Wirth 2004] that achieves a factor of O(log n). 2) Bounded degree 2-CSP's: under randomized reductions, for sufficiently large $d>0$, it is NP-hard to approximate the value of 2-CSPs in which each variable appears in at most d constraints within factor $(1-o(1))d/2$ improving upon a recent result of [Lee-Manurangsi 2023]. 3) Improved hardness results for connectivity problems: using results of [Laekhanukit 2014] and [Manurangsi 2019], we deduce improved hardness results for the Rooted k-Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity k-Route Cut Problem.