  For spin systems, such as the $q$-colorings and independent-set models,
approximating the partition function in the so-called non-uniqueness region,
where the model exhibits long-range correlations, is typically computationally
hard for bounded-degree graphs. We present new algorithmic results for
approximating the partition function and sampling from the Gibbs distribution
for spin systems in the non-uniqueness region on random regular bipartite
graphs. We give an $\mathsf{FPRAS}$ for counting $q$-colorings for even
$q=O\big(\tfrac{\Delta}{\log{\Delta}}\big)$ on almost every $\Delta$-regular
bipartite graph. This is within a factor $O(\log{\Delta})$ of the sampling
algorithm for general graphs in the uniqueness region and improves
significantly upon the previous best bound of
$q=O\big(\tfrac{\sqrt{\Delta}}{(\log\Delta)^2}\big)$ by Jenssen, Keevash, and
Perkins (SODA'19). Analogously, for the hard-core model on independent sets
weighted by $\lambda>0$, we present an $\mathsf{FPRAS}$ for estimating the
partition function when $\lambda=\Omega\big(\tfrac{\log{\Delta}}{\Delta}\big)$,
which improves upon previous results by an $\Omega(\log \Delta)$ factor. Our
results for the colorings and hard-core models follow from a general result
that applies to arbitrary spin systems. Our main contribution is to show how to
elevate probabilistic/analytic bounds on the marginal probabilities for the
typical structure of phases on random bipartite regular graphs into efficient
algorithms, using the polymer method. We further show evidence that our result
for colorings is within a constant factor of best possible using current
polymer-method approaches.
