Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

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(g.,") 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.