  We give a nearly linear-time algorithm to approximately sample satisfying
assignments in the random $k$-SAT model when the density of the formula scales
exponentially with $k$. The best previously known sampling algorithm for the
random $k$-SAT model applies when the density $\alpha=m/n$ of the formula is
less than $2^{k/300}$ and runs in time $n^{\exp(\Theta(k))}$. Here $n$ is the
number of variables and $m$ is the number of clauses. Our algorithm achieves a
significantly faster running time of $n^{1 + o_k(1)}$ and samples satisfying
assignments up to density $\alpha\leq 2^{0.039 k}$.
  The main challenge in our setting is the presence of many variables with
unbounded degree, which causes significant correlations within the formula and
impedes the application of relevant Markov chain methods from the
bounded-degree setting. Our main technical contribution is a $o_k(\log n )$
bound of the sum of influences in the $k$-SAT model which turns out to be
robust against the presence of high-degree variables. This allows us to apply
the spectral independence framework and obtain fast mixing results of a
uniform-block Glauber dynamics on a carefully selected subset of the variables.
The final key ingredient in our method is to take advantage of the sparsity of
logarithmic-sized connected sets and the expansion properties of the random
formula, and establish relevant connectivity properties of the set of
satisfying assignments that enable the fast simulation of this Glauber
dynamics.
  Our results also allow us to conclude that, with high probability, a random
$k$-CNF formula with density at most $2^{0.227 k}$ has a giant component of
solutions that are connected in a graph where solutions are adjacent if they
have Hamming distance $O_k(\log n)$. We are also able to deduce looseness
results for random $k$-CNFs in the same regime.
