TY - GEN
T1 - On approximability of satisfiable k-CSPs
T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
AU - Bhangale, Amey
AU - Khot, Subhash
AU - Minzer, Dor
N1 - Funding Information:
∗Research funded by NSF grant CCF-1813438, Simons Investigator Award, and Simons Collaboration on Algorithms and Geometry. 2Research supported by a Sloan Research Fellowship.
Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/9/6
Y1 - 2022/9/6
N2 - We consider the P-CSP problem for 3-ary predicates P on satisfiable instances. We show that under certain conditions on P and a (1,s) integrality gap instance of the P-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness s+ϵ, for every constant ϵ>0. Compared to Ragahvendra's result [STOC, 2008], we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman, Khot, and Minzer [ITCS, 2021]. Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable k-ary CSP. At the heart of the reduction is our main analytical lemma for a class of 3-ary predicates, which is a generalization of a lemma by Mossel [Geometric and Functional Analysis, 2010]. The lemma and a further generalization of it that we conjecture may be of independent interest.
AB - We consider the P-CSP problem for 3-ary predicates P on satisfiable instances. We show that under certain conditions on P and a (1,s) integrality gap instance of the P-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness s+ϵ, for every constant ϵ>0. Compared to Ragahvendra's result [STOC, 2008], we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman, Khot, and Minzer [ITCS, 2021]. Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable k-ary CSP. At the heart of the reduction is our main analytical lemma for a class of 3-ary predicates, which is a generalization of a lemma by Mossel [Geometric and Functional Analysis, 2010]. The lemma and a further generalization of it that we conjecture may be of independent interest.
KW - constraint satisfaction problems
KW - hardness of approximation
KW - non-abelian groups
UR - http://www.scopus.com/inward/record.url?scp=85130571149&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85130571149&partnerID=8YFLogxK
U2 - 10.1145/3519935.3520028
DO - 10.1145/3519935.3520028
M3 - Conference contribution
AN - SCOPUS:85130571149
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 976
EP - 988
BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Leonardi, Stefano
A2 - Gupta, Anupam
PB - Association for Computing Machinery
Y2 - 20 June 2022 through 24 June 2022
ER -