SDPs and Robust Satisfiability of Promise CSP
SDPs and Robust Satisfiability of Promise CSP
复制标题
SDP 和 Promise CSP 的鲁棒可满足性
DOI：
10.1145/3564246.3585180
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Sandeep, Sai
中科院分区：
文献类型：
--
作者：
Brakensiek, Joshua;Guruswami, Venkatesan;Sandeep, Sai
对于约束满足问题（CSP），一个鲁棒的满足算法是在接近可满足的实例上输出一个满足大多数约束的分配。已知，允许有效鲁棒满足算法的csp恰恰是有界宽度的csp，即可以用简单的局部一致性算法(如。（2-SAT或Horn-SAT在布尔情况下）。虽然有界宽度CSP的精确可满足性可以用组合算法来检验，但鲁棒算法是基于正则半确定规划（SDP）松弛的舍入。在这项工作中，我们启动了对承诺csp的鲁棒满意算法的研究，这是最近受到广泛关注的csp的广泛推广。其动机是将理论扩展到csp之外，以及更好地理解sdp的力量。在某些一般条件下，即存在多数或交替阈值多态性，我们提出了鲁棒的SDP舍入算法。在硬度方面，我们证明了这种多态性的缺乏使得PCSP对所有对称布尔谓词都是困难的。我们的方法涉及一种新颖的方法，通过球体的某些颜色的缺失来论证SDP间隙，并与球体拉姆齐理论相联系。我们推测具有鲁棒满足算法的pcsp正是那些规范SDP的可行性意味着（精确）可满足性的pcsp。我们还给出了一个精确的代数条件，称为仆从表征，其中pcsp具有后者的性质。
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be checked by a simple local consistency algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact satisfiability of a bounded width CSP can be checked by combinatorial algorithms, the robust algorithm is based on rounding a canonical Semi Definite Programming(SDP) relaxation.In this work, we initiate the study of robust satisfaction algorithms for promise CSPs, which are a vast generalization of CSPs that have received much attention recently. The motivation is to extend the theory beyond CSPs, as well as to better understand the power of SDPs. We present robust SDP rounding algorithms under some general conditions, namely the existence of majority or alternating threshold polymorphisms. On the hardness front, we prove that the lack of such polymorphisms makes the PCSP hard for all pairs of symmetric Boolean predicates. Our method involves a novel method to argue SDP gaps via the absence of certain colorings of the sphere, with connections to sphere Ramsey theory.We conjecture that PCSPs with robust satisfaction algorithms are precisely those for which the feasibility of the canonical SDP implies (exact) satisfiability. We also give a precise algebraic condition, known as a minion characterization, of which PCSPs have the latter property.
登录
查看更多内容
顶点覆盖Lovasz-Schrijver SDP松弛的线性圆下界
DOI：
--
发表时间：
2007
期刊：
Cybersecurity and Cyberforensics Conference
影响因子：
--
作者：
Grant Schoenebeck;Luca Trevisan;Madhur Tulsiani
通讯作者：
Madhur Tulsiani
Sherali-Adams 放宽对于普通价值 CSP 的作用
DOI：
--
发表时间：
2016
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Johan Thapper;Stanislav Živný
通讯作者：
Stanislav Živný
约束满足问题：复杂性和近似性（Dagstuhl 研讨会 18231）
DOI：
--
发表时间：
2018
期刊：
Dagstuhl Reports
影响因子：
--
作者：
Martin Grohe;V. Guruswami;Stanislav Živný
通讯作者：
Stanislav Živný
普通价值 CSP 的 SDP 放宽限制
DOI：
--
发表时间：
2016
期刊：
Logic in Computer Science
影响因子：
--
作者：
Johan Thapper;Stanislav Živný
通讯作者：
Stanislav Živný
论拉姆齐球体集
DOI：
--
发表时间：
1995
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
J. Matoušek;V. Rödl
通讯作者：
V. Rödl