The Algorithmic Phase Transition of Random $k$-SAT for Low Degree Polynomials
This addresses a fundamental algorithmic bottleneck in constraint satisfaction problems for theoretical computer science, providing the first hardness result for a broad class of algorithms near the state-of-the-art performance.
The paper tackles the problem of efficiently finding satisfying assignments for random k-SAT formulas at high clause densities, proving that low-degree polynomial algorithms fail at densities around (1+o_k(1)) κ^* 2^k log k / k, where κ^* ≈ 4.911, which is a constant factor higher than the best known algorithm's threshold.
Let $Φ$ be a uniformly random $k$-SAT formula with $n$ variables and $m$ clauses. We study the algorithmic task of finding a satisfying assignment of $Φ$. It is known that satisfying assignments exist with high probability up to clause density $m/n = 2^k \log 2 - \frac12 (\log 2 + 1) + o_k(1)$, while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan, finds a satisfying assignment at the much lower clause density $(1 - o_k(1)) 2^k \log k / k$. This prompts the question: is it possible to efficiently find a satisfying assignment at higher clause densities? We prove that the class of low degree polynomial algorithms cannot find a satisfying assignment at clause density $(1 + o_k(1)) κ^* 2^k \log k / k$ for a universal constant $κ^* \approx 4.911$. This class encompasses Fix, message passing algorithms including Belief and Survey Propagation guided decimation (with bounded or mildly growing number of rounds), and local algorithms on the factor graph. This is the first hardness result for any class of algorithms at clause density within a constant factor of that achieved by Fix. Our proof establishes and leverages a new many-way overlap gap property tailored to random $k$-SAT.