Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

We present the current fastest deterministic algorithm for k-SAT, improving the upper bound (2-2/k)n + o(n) dues to Moser and Scheder [STOC'11]. The algorithm combines a branching algorithm with the derandomized local search, whose analysis relies on a special sequence of clauses called chain, and a generalization of covering code based on linear programming. We also provide a more ingenious branching algorithm for 3-SAT to establish the upper bound 1.32793n, improved from 1.3303n.