Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-027 | 18th February 2024 03:50

Near Optimal Alphabet-Soundness Tradeoff PCPs


Authors: Dor Minzer, Kai Zhe Zheng
Publication: 18th February 2024 04:22
Downloads: 458


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.

ISSN 1433-8092 | Imprint