  It has been hypothesized that $k$-SAT is hard to solve for randomly chosen
instances near the "critical threshold", where the clause-to-variable ratio is
$2^k \ln 2-\theta(1)$. Feige's hypothesis for $k$-SAT says that for all
sufficiently large clause-to-variable ratios, random $k$-SAT cannot be refuted
in polynomial time. It has also been hypothesized that the worst-case $k$-SAT
problem cannot be solved in $2^{n(1-\omega_k(1)/k)}$ time, as multiple known
algorithmic paradigms (backtracking, local search and the polynomial method)
only yield an $2^{n(1-1/O(k))}$ time algorithm. This hypothesis has been called
the "Super-Strong ETH", modeled after the ETH and the Strong ETH.
  Our main result is a randomized algorithm which refutes the Super-Strong ETH
for the case of random $k$-SAT, for any clause-to-variable ratio. Given any
random $k$-SAT instance $F$ with $n$ variables and $m$ clauses, our algorithm
decides satisfiability for $F$ in $2^{n(1-\Omega(\log k)/k)}$ time, with high
probability. It turns out that a well-known algorithm from the literature on
SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane
(1998).
