  Random constraint satisfaction problems (CSPs) are known to exhibit threshold
phenomena: given a uniformly random instance of a CSP with $n$ variables and
$m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be
unsatisfiable with high probability. Strong refutation is the problem of
certifying that no variable assignment satisfies more than a constant fraction
of clauses; this is the natural algorithmic problem in the unsatisfiable regime
(when $m/n = \omega(1)$).
  Intuitively, strong refutation should become easier as the clause density
$m/n$ grows, because the contradictions introduced by the random clauses become
more locally apparent. For CSPs such as $k$-SAT and $k$-XOR, there is a
long-standing gap between the clause density at which efficient strong
refutation algorithms are known, $m/n \ge \widetilde O(n^{k/2-1})$, and the
clause density at which instances become unsatisfiable with high probability,
$m/n = \omega (1)$.
  In this paper, we give spectral and sum-of-squares algorithms for strongly
refuting random $k$-XOR instances with clause density $m/n \ge \widetilde
O(n^{(k/2-1)(1-\delta)})$ in time $\exp(\widetilde O(n^{\delta}))$ or in
$\widetilde O(n^{\delta})$ rounds of the sum-of-squares hierarchy, for any
$\delta \in [0,1)$ and any integer $k \ge 3$. Our algorithms provide a smooth
transition between the clause density at which polynomial-time algorithms are
known at $\delta = 0$, and brute-force refutation at the satisfiability
threshold when $\delta = 1$. We also leverage our $k$-XOR results to obtain
strong refutation algorithms for SAT (or any other Boolean CSP) at similar
clause densities. Our algorithms match the known sum-of-squares lower bounds
due to Grigoriev and Schonebeck, up to logarithmic factors.
  Additionally, we extend our techniques to give new results for certifying
upper bounds on the injective tensor norm of random tensors.
