On approximability of satisfiable k-CSPs: I

Amey Bhangale, Subhash Khot, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
EditorsStefano Leonardi, Anupam Gupta
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781450392648
StatePublished - Sep 6 2022
Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
Duration: Jun 20 2022Jun 24 2022

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022


  • constraint satisfaction problems
  • hardness of approximation
  • non-abelian groups

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On approximability of satisfiable k-CSPs: I'. Together they form a unique fingerprint.

Cite this