ECCC-Report TR24-027https://eccc.weizmann.ac.il/report/2024/027Comments and Revisions published for TR24-027en-usSun, 18 Feb 2024 04:22:16 +0200
Paper TR24-027
| Near Optimal Alphabet-Soundness Tradeoff PCPs |
Dor Minzer,
Kai Zhe Zheng
https://eccc.weizmann.ac.il/report/2024/027 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 with alphabet size $q$, improving upon a result of Chan [Cha16]. 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 and Safra [KS13] and nearly matches the performance of the best known approximation algorithm [Meg01, NRT99, CW04] 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))\frac{d}{2}$, improving upon a recent result of Lee and Manurangsi [LM23].
3. Improved hardness results for connectivity problems: using results of Laekhanukit [Lae14] and Manurangsi [Man19], 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.Sun, 18 Feb 2024 04:22:16 +0200https://eccc.weizmann.ac.il/report/2024/027