论文标题
用离群值近似CSP
Approximating CSPs with Outliers
论文作者
论文摘要
约束满意度问题（CSP）在理论计算机科学中无处不在。我们研究了strongcsps的问题，即大型诱导子构度具有令人满意的分配的情况。更正式的是，给定一个CSP实例$ψ（V，E，[K]，\ {π_{IJ} \} _ {（I，J）\ in E}）$由一组顶点$ v $组成的$ V $，一组edges $ e $，Alphabet $ [k] $ a $ k] $ k] $ k] $（i，j）\在e $中，此问题的目标是计算最大的子集$ s \ subseteq v $，以便在$ s $上诱导的实例具有满足所有约束的任务。 在本文中，我们研究了在强大的约束图满足轻度扩展属性时，在strongcsp框架下针对独特游戏和相关问题的近似算法。特别是，我们表明，给定一个强大的独特游戏实例，其最佳解决方案$ s^*$在常规的低阈值等级图上支持，存在一种算法，该算法在阈值等级时在时间指数上运行，并恢复了一个可满足的大型子内结构，其大小在标签设置大小和图表的最大程度上是独立的。我们的算法结合了Barak-Raghavendra-Steurer（focs'11），Guruswami-Sinop（focs'11）的技术，并在最佳集合的阈值等级中及时运行。我们算法的关键组成部分是基于新的阈值谱分解，该分解用于计算“小”阈值等级的“大”诱导子图；我们的技术以Oveis Gharan和Rezaei（Soda'17）的工作为基础，并且可能具有独立的利益。
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of StrongCSPs, i.e. instances where a large induced sub-instance has a satisfying assignment. More formally, given a CSP instance $Ψ(V, E, [k], \{Π_{ij}\}_{(i,j) \in E})$ consisting of a set of vertices $V$, a set of edges $E$, alphabet $[k]$, a constraint $Π_{ij} \subset [k] \times [k]$ for each $(i,j) \in E$, the goal of this problem is to compute the largest subset $S \subseteq V$ such that the instance induced on $S$ has an assignment that satisfies all the constraints. In this paper, we study approximation algorithms for Unique Games and related problems under the StrongCSP framework when the underlying constraint graph satisfies mild expansion properties. In particular, we show that given a Strong Unique Games instance whose optimal solution $S^*$ is supported on a regular low threshold rank graph, there exists an algorithm that runs in time exponential in the threshold rank, and recovers a large satisfiable sub-instance whose size is independent on the label set size and maximum degree of the graph. Our algorithm combines the techniques of Barak-Raghavendra-Steurer (FOCS'11), Guruswami-Sinop (FOCS'11) with several new ideas and runs in time exponential in the threshold rank of the optimal set. A key component of our algorithm is a new threshold rank based spectral decomposition, which is used to compute a "large" induced subgraph of "small" threshold rank; our techniques build on the work of Oveis Gharan and Rezaei (SODA'17) and could be of independent interest.
