arXiv preprint ·
Deterministic Approximation of the Total Variation Distance Between Spin Systems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
The chromatic number of the associahedron: simple and logarithmic
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.