The Quest for Strong Inapproximability Results with Perfect Completeness
The Quest for Strong Inapproximability Results with Perfect Completeness
复制标题
追求完美完整性的强不可近似性结果
DOI：
10.1145/3459668
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Guruswami, Venkatesan
中科院分区：
文献类型：
--
作者：
Brakensiek, Joshua;Guruswami, Venkatesan
唯一对策猜想确定了所有约束满足问题（CSP）的近似性，表明自然的半确定规划松弛为任何CSP提供了最佳最坏情况近似比。然而，由于Unique Games Conjecture固有的不完备性，这一优美的画面并不适用于完全可满足的CSP实例。这项工作的动机是为了更好地理解完全可满足的csp实例的近似性。我们证明了标签覆盖的“几乎唯一”版本可以在一个常数因子内近似于一个可满足的实例。我们的主要概念贡献是一个（超图）版本的标签覆盖的公式，我们称之为v标签覆盖。假设一个关于V标签覆盖在完全可满足实例上的不逼近性的猜想，我们证明了以下的意义：•存在一个绝对常数，使得分叉≥3，给定一个布尔兰克- csp的可满足实例，很难找到一个满足超过2/2k个约束分数的赋值。•给定k-一致超图，k≥2，对于所有ε > 0，很难判断它是q-强可着色的，还是没有ε分数顶点的独立集，其中q=≤≤k+√k-1/2²。•给定k-一致超图，k≥3，对于所有ε > 0，很难判断它是(k-1)-彩虹可着色的，还是没有具有ε分数顶点的独立集。
The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture.This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we callV Label Cover. Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications:• There is an absolute constantc0such that fork≥ 3, given a satisfiable instance of Booleank-CSP, it is hard to find an assignment satisfying more thanc0k2/2kfraction of the constraints.• Given ak-uniform hypergraph,k≥ 2, for all ε > 0, it is hard to tell if it isq-strongly colorable or has no independent set with an ε fraction of vertices, whereq=⌈k+√k-1/2⌉.• Given ak-uniform hypergraph,k≥ 3, for all ε > 0, it is hard to tell if it is (k-1)-rainbow colorable or has no independent set with an ε fraction of vertices.
登录
查看更多内容
在 2 色超图中寻找独立集和可满足 CSP 的难度
DOI：
--
发表时间：
2013
期刊：
Cybersecurity and Cyberforensics Conference
影响因子：
--
作者：
Rishi Saket
通讯作者：
Rishi Saket
影响因子：
1
作者：
Sangxia Huang
通讯作者：
Sangxia Huang
降低 Khot-Saket 超图着色硬度降低的均匀性
DOI：
--
发表时间：
2014
期刊：
Chicago journal of theoretical computer science
影响因子：
--
作者：
G. Varma
通讯作者：
G. Varma
查询高效且完整的 PCP
DOI：
--
发表时间：
2001
期刊：
Proceedings IEEE International Conference on Cluster Computing
影响因子：
--
作者：
J. Håstad;Subhash Khot
通讯作者：
Subhash Khot
关于没有三项数学级数的 F nq 的大子集
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
J. Ellenberg;D. Gijswijt
通讯作者：
D. Gijswijt