| Summary: | We show that for all > 0, for su ciently large prime power
∈ N, for all > 0, it is NP-hard to distinguish whether a 2-Prover1-Round projection game with alphabet size has value at least
1 − , or value at most 1/
1−
. This establishes a nearly optimal
alphabet-to-soundness tradeo for 2-query PCPs with alphabet
size , improving upon a result of [Chan 2016]. Our result has the
following implications:
(1) Near optimal hardness for Quadratic Programming: it is NPhard to approximate the value of a given Boolean Quadratic
Program within factor (log)
1− (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-RoosTerlaky 1999 Charikar-Wirth 2004] that achieves a factor of
(log).
(2) Bounded degree 2-CSP’s: under randomized reductions, for
su ciently large > 0, it is NP-hard to approximate the
value of 2-CSPs in which each variable appears in at most
constraints within factor (1 − (1))
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 -Connectivity
Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity -Route Cut Problem.
|
|---|