2024/04/11 by Minzer, Dor, Zheng, Kai Zhe · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2404.07441
We show that for all ε>0, for sufficiently large q∈ℕ power of 2, for all δ>0, it is NP-hard to distinguish whether a given 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/q1-ε. This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q, improving upon a result of [Chan, Journal of the ACM 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 improves upon a result of [Khot, Safra, ToC 2013] and nearly matches the performance of the best known algorithms due to [Megretski, IWOTA 2000], [Nemirovski, Roos, Terlaky, Mathematical programming 1999] and [Charikar, Wirth, FOCS 2004] that achieve O(log n) approximation ratio. 2) Bounded degree 2-CSPs: 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 result of [Lee, Manurangsi, ITCS 2024]. 3) Improved hardness results for connectivity problems: using results of [Laekhanukit, SODA 2014] and [Manurangsi, Inf. Process. Lett., 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.