On Approximability of Satisfiable k-CSPs: I
On Approximability of Satisfiable k-CSPs: I
复制标题
关于可满足 k-CSP 的近似性：I
DOI：
10.1145/3519935.3520028
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Minzer, Dor
中科院分区：
文献类型：
--
作者：
Bhangale, Amey;Khot, Subhash;Minzer, Dor
本文考虑了3元谓词P在可满足实例上的P-CSP问题。我们证明了在P和（1，s）完整性缺口的一定条件下，P-CSP问题可以转化为一个独裁与准随机性的检验，具有完美的完备性和soundnesss+ε，对每个常数ε>0.与Ragahvendra的结果[STOC，2008]相比，我们没有失去完美的完整性。这是特别有趣的，因为这个测试意味着可满足的约束满足问题的新的硬度结果，假设Braverman，Khot和Minzer的丰富2对1游戏猜想[ITCS，2021]。我们的结果可以被看作是一个潜在的长期挑战性计划的第一步，该计划旨在表征每个可满足的k-ary CSP的最优不可逼近性。约简的核心是我们对一类3-ary谓词的主要分析引理，这是Mossel [Geometric and Functional Analysis，2010]引理的推广。引理和它的进一步推广，我们推测可能是独立的利益。
We consider theP-CSP problem for 3-ary predicatesPon satisfiable instances. We show that under certain conditions onPand a (1,s)integrality gapinstance of theP-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundnesss+ε, 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 satisfiablek-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.