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

arXiv: https://arxiv.org/abs/1804.07901 · HTML: https://mlsanity.com/paper/1804.07901/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Algorithms for Boolean Satisfiability](https://mlsanity.com/paper/2505.06146/) (2025)

## Abstract (arXiv)

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.