Abstract
In this talk, I'll 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 the negation pattern on each literal randomized with some small probability (say 0.1). Note that the clause structure in the resulting instance is completely arbitrary, only the literal patterns are perturbed. For an n-variable smoothed instance of a k-ary CSP, our algorithm runs in n^{O(\ell)} 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} poly log n. 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 new connection between sub-exponential time CSP-refutation algorithms obtained via our algorithm and the existence of polynomial-size combinatorial certificates of unsatisfiability. Using this connection, we prove Feige's 2008 conjecture on the existence of "even covers" in sufficiently dense hypergraphs -- a claim that generalizes the well-known Moore bound on the girth of graphs to arbitrary k-uniform hypergraphs. As a corollary, we obtain that smoothed instances of 3-sat with arbitrary clause structure and ~n^{1.4} (<< n^{1.5}, the threshold for best known efficient refutation algorithms) constraints admit polynomial-size certificates of unsatisfiability (whp). We also prove an appropriate generalization to all k-CSPs. This extends the celebrated work of Feige, Kim and Ofek who proved a similar result for fully random instances of 3-sat with n^{1.4} clauses. FKO's proof uses a 2nd-moment-method based argument that strongly exploits the randomness of the clause structure. Our proof gives a (perhaps simpler) argument that works for ``worst-case" clause structures. Taken together, our results show that smoothed instances with arbitrary clause structure (and considerably less randomness) enjoy the same thresholds for both refutation algorithms and certificates of unsatisfiability. Based on joint work with Venkat Guruswami (CMU) and Peter Manohar (CMU).