Description:
<jats:p>
Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal
<jats:italic>O(n</jats:italic>
log
<jats:italic>n)</jats:italic>
sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using
<jats:italic>
L
<jats:sup>p</jats:sup>
</jats:italic>
-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity of
<jats:italic>
L
<jats:sup>p</jats:sup>
</jats:italic>
-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the
<jats:italic>
L
<jats:sup>p</jats:sup>
</jats:italic>
-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph
<jats:italic>G (n, d/n)</jats:italic>
, where the previously known algorithms run in time
<jats:italic>
n
<jats:sup>O</jats:sup>
</jats:italic>
(log
<jats:italic>d</jats:italic>
) or applied only to large
<jats:italic>d</jats:italic>
. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant
<jats:italic>d</jats:italic>
, throughout the uniqueness regime.
</jats:p>