  Let $\Phi$ be a uniformly random $k$-SAT formula with $n$ variables and $m$
clauses. We study the algorithmic task of finding a satisfying assignment of
$\Phi$. 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)) \kappa^* 2^k \log k / k$
for a universal constant $\kappa^* \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.
