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 𝑛-variable smoothed instance of a 𝑘-arity CSP, our algorithm runs in 𝑛 𝑂(ℓ ) 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 Õ(𝑛)( 𝑛 ℓ )

𝑘 2 -1 . This matches, up to polylogarithmic factors in 𝑛, 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 connection between the analysis of our refutation algorithm in the significantly "randomness starved" setting of semi-random 𝑘-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 𝑛 𝑘/2 , extending the celebrated result for random 3-SAT of Feige, Kim and Ofek [FKO06].