A novel weighting scheme for random $k$-SAT

Zongsheng Gao, Jun Liu, Ke Xu

Consider a random $k$-CNF formula $F_k(n,rn)$ with $n$ variables and $rn$ clauses. For every truth assignment $\sigma \in \{0,1{\}}^n$ and every clause $c=\ell_{1}\vee\cdots\vee\ell_…