  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(\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 $\tilde{O}(n) (\frac{n}{\ell})^{\frac{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 [RRS17].
  We also make a surprising new connection between our algorithm and even
covers in hypergraphs, which we use 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
[FKO06].
