<p>We consider the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$P$</EquationSource> <EquationSource Format="MATHML"><math> <mi>P</mi> </math></EquationSource> </InlineEquation>-CSP problem for 3-ary predicates <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$P$</EquationSource> <EquationSource Format="MATHML"><math> <mi>P</mi> </math></EquationSource> </InlineEquation> on satisfiable instances. We show that under certain conditions on <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$P$</EquationSource> <EquationSource Format="MATHML"><math> <mi>P</mi> </math></EquationSource> </InlineEquation> and a <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(1,s)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> integrality gap instance of the <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$P$</EquationSource> <EquationSource Format="MATHML"><math> <mi>P</mi> </math></EquationSource> </InlineEquation>-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$s+\epsilon$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>+</mo> <mi>ϵ</mi> </mrow> </math></EquationSource> </InlineEquation>, for every constant <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\epsilon>0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. Compared to Ragahvendra (in: Proceedings of the fortieth annual ACMsymposium on theory of computing (STOC), pp 245–254, 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 et al. (in: Lee JR (ed) Volume 185 of Leibniz international proceedingsin informatics (LIPIcs), 27:1–27:20. Schloss Dagstuhl–Leibniz-Zentrumfür Informatik, Dagstuhl, 2021b.<a href="https://drops.dagstuhl.de/opus/volltexte/2021/13566">https://drops.dagstuhl.de/opus/volltexte/2021/13566</a>).Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$k$</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-ary CSP.</p><p>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 (Geom Funct Anal 19(6):1713–1756, 2010). The lemma and a further generalization of it that we conjecture may be of independent interest.</p>

On approximability of Satisfiable $k$-CSPs: I

期刊论文
出版模式：

开放获取
发表日期：

2025年7月22日

查看全文

Amey Bhangale,
Subhash Khot,
Dor Minzer

摘要

We consider the $P$ $P$ -CSP problem for 3-ary predicates $P$ $P$ on satisfiable instances. We show that under certain conditions on $P$ $P$ and a $(1,s)$ $(1, s)$ integrality gap instance of the $P$ $P$ -CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\epsilon$ $s + ϵ$ , for every constant $\epsilon>0$ $ϵ > 0$ . Compared to Ragahvendra (in: Proceedings of the fortieth annual ACMsymposium on theory of computing (STOC), pp 245–254, 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 et al. (in: Lee JR (ed) Volume 185 of Leibniz international proceedingsin informatics (LIPIcs), 27:1–27:20. Schloss Dagstuhl–Leibniz-Zentrumfür Informatik, Dagstuhl, 2021b.https://drops.dagstuhl.de/opus/volltexte/2021/13566).Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable $k$ $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 (Geom Funct Anal 19(6):1713–1756, 2010). The lemma and a further generalization of it that we conjecture may be of independent interest.

On approximability of Satisfiable \(k\)-CSPs: I

摘要