Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
复制标题
DOI：
10.1145/3519935.3519955
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
V. Guruswami;Pravesh Kothari;Peter Manohar
中科院分区：
文献类型：
--
作者：
V. Guruswami;Pravesh Kothari;Peter Manohar
我们提出了一种对所有布尔csp的平滑实例进行强驳斥的算法。平滑模型是最差情况和平均情况输入模型之间的混合体，其中输入是CSP的任意实例，只有文字的否定模式以小概率重新随机化。对于一个n变量k-arity CSP的光滑实例，我们的算法在n^O(r)时间内运行，并且在约束数量至少为Õ(n) (n/ell)^（k/2 - 1）的情况下，以高概率成功地将可满足约束的最佳分数边界离1。这与n中的多对数因子相匹配，在运行时间和最先进的算法的约束数量之间进行权衡，以反驳csp的完全随机实例。我们还在半随机k-XOR的显著“随机性匮乏”设置下对我们的反驳算法的分析与最坏情况超图中偶覆盖的存在之间建立了令人惊讶的联系。我们利用这一联系积极地解决了Feige的2008猜想——一个关于在足够密集的超图中存在偶数覆盖的极值组合猜想，它推广了众所周知的图周长摩尔界。作为一个推论，我们证明了多项式大小的驳斥证据存在于任意光滑的CSP实例中，其约束数量的多项式因子低于n^（k/2）的“谱阈值”，扩展了Feige， Kim和Ofek的随机3-SAT的著名结果。
We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(ℓ) time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2 - 1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs. We also make a surprising connection between the analysis of our refutation algorithm in the significantly ”randomness starved” setting of semi-random k-XOR and the existence of even covers in worst-case hypergraphs. We use this connection to positively resolve Feige’s 2008 conjecture – an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the ”spectral threshold” of n^(k/2), extending the celebrated result for random 3-SAT of Feige, Kim and Ofek.