  Propositional satisfiability (SAT) is one of the most fundamental problems in
computer science. The worst-case hardness of SAT lies at the core of
computational complexity theory. The average-case analysis of SAT has triggered
the development of sophisticated rigorous and non-rigorous techniques for
analyzing random structures.
  Despite a long line of research and substantial progress, nearly all
theoretical work on random SAT assumes a uniform distribution on the variables.
In contrast, real-world instances often exhibit large fluctuations in variable
occurrence. This can be modeled by a scale-free distribution of the variables,
which results in distributions closer to industrial SAT instances.
  We study random k-SAT on n variables, $m=\Theta(n)$ clauses, and a power law
distribution on the variable occurrences with exponent $\beta$. We observe a
satisfiability threshold at $\beta=(2k-1)/(k-1)$. This threshold is tight in
the sense that instances with $\beta\le(2k-1)/(k-1)-\varepsilon$ for any
constant $\varepsilon>0$ are unsatisfiable with high probability (w.h.p.). For
$\beta\geq(2k-1)/(k-1)+\varepsilon$, the picture is reminiscent of the uniform
case: instances are satisfiable w.h.p. for sufficiently small constant
clause-variable ratios $m/n$; they are unsatisfiable above a ratio $m/n$ that
depends on $\beta$.
