Deterministic Approximation of the Total Variation Distance Between Spin Systems

Abstract

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-\eta)\lambda_{\mathrm c}(\Delta)]^V$, where $b>0$ and $\eta\in(0,1)$ are fixed and $\lambda_{\mathrm c}(\Delta)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.