Peter Manohar

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

2022

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 …