Robin Moser and Dominik Scheder have put an end to the stream of slight improvements in derandomizing Schöning’s randomized k-SAT algorithm from 1999.
In A Full Derandomization of Schöning’s k-SAT Algorithm, Moser and Scheder show how to achieve worst-case runtime as close as desired to the runtime of the randomized algorithm, for any . For , this is .
The paper notably rephrases Schöning’s search problem as
|Input:||-CNF formula with variables, an assignment , a natural number , and a promise that there is a satisfying assignment within Hamming distance of .|
|Objective:||find a satisfying assignment for F.|
Note that the satisfying assignment does not have to be in the -ball centered at .
Instead of using a Boolean covering code (with a domain of two values) as is done by Dantsin et al., Moser and Scheder use a covering code with a domain containing more values. Larger domains allow a closer approximation to the runtime bound.
A neat application (Corollary 13) is that it is possible to solve the constraint satisfaction problem with domain size and arity in time . In contrast, a straightforward brute-force approach takes time.