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 -