arXiv preprint ·
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).
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
On the Equivalence of Stochastic Control and Path Space Formulations for Schrödinger Bridges over Compact Connected Lie Groups
Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
Yet another asymptotic formula for implied volatility
Exact calibration of structural models via time-change
Gaussian Normalized Coordinates and Risk-Neutral CDF Deformations
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.