The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

Abstract

Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Phi$</tex> be a uniformly random <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> -SAT formula with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> variables and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> clauses. We study the algorithmic task of finding a satisfying assignment of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Phi$</tex> . It is known that satisfying assignments exist with high probability up to clause density <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m/n=2^{k} \log 2-\frac{1}{2}(\log 2+1)+o_{k}(1)$</tex> , while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan [1], finds a satisfying assignment at the much lower clause density <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-o_{k}(1))2^{k}\log k/k$</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+o_{k}(1))\kappa^{\ast}2^{k}\log k/k$</tex> for a universal constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa^{\ast}\approx 4.911$</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> -SAT.

Topics & Concepts