论文标题
强烈反驳所有半随机布尔CSP
Strongly refuting all semi-random Boolean CSPs
论文作者
论文摘要
我们给出了有效的算法，以强烈反驳所有布尔约束满意度问题的实例\ emph {semi-random}。我们的算法匹配所需的约束数量（最终是聚类因素）是有效反驳完全随机实例的最著名界限。我们的主要技术贡献是在$ n $变量上强烈反驳布尔$ k $ xor问题的算法，该实例具有$ \ widetilde {o}（n^{k/2}）$约束。 （在半随机$ K $ -XOR实例中，方程可以是任意的，只有右侧是随机的。） 我们的主要见解之一是确定使光谱反驳工作的随机XOR实例的简单组合属性。我们的方法涉及采用不满足此属性的实例（即，是\ emph {not} pseudorandom）并将其简化为$ 2 $ -XOR实例的分区集合。我们使用精心选择的二次形式作为代理来分析这些子发现，进而通过光谱方法和半芬矿编程的组合进行了界定。对光谱界的分析仅依赖于现成的基质伯恩斯坦不等式。即使对于纯粹随机的情况，与依赖于特定于问题的痕量计算的文献相比，这也导致了更短的证明。
We give an efficient algorithm to strongly refute \emph{semi-random} instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm matches (up to polylogarithmic factors) the best-known bounds for efficient refutation of fully random instances. Our main technical contribution is an algorithm to strongly refute semi-random instances of the Boolean $k$-XOR problem on $n$ variables that have $\widetilde{O}(n^{k/2})$ constraints. (In a semi-random $k$-XOR instance, the equations can be arbitrary and only the right-hand sides are random.) One of our key insights is to identify a simple combinatorial property of random XOR instances that makes spectral refutation work. Our approach involves taking an instance that does not satisfy this property (i.e., is \emph{not} pseudorandom) and reducing it to a partitioned collection of $2$-XOR instances. We analyze these subinstances using a carefully chosen quadratic form as a proxy, which in turn is bounded via a combination of spectral methods and semidefinite programming. The analysis of our spectral bounds relies only on an off-the-shelf matrix Bernstein inequality. Even for the purely random case, this leads to a shorter proof compared to the ones in the literature that rely on problem-specific trace-moment computations.
