arXiv preprint ·
The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth. Given any $n$-vertex graph $G$, let $k_η= k_η(G)$ count normalized-Laplacian eigenvalues strictly below $η$. For $\varepsilon > 0$, an $\varepsilon$-approximate counting algorithm outputs an estimate $\widehat Z$ of the partition function $Z$ satisfying $(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z$ with probability at least $3/4$. An $\varepsilon$-approximate sampling algorithm outputs a configuration whose distribution is within total variation distance $\varepsilon$ of the target distribution. We give the following results: (a) Ferromagnetic Potts. Fix $q\ge2$ and $η\in(0,1]$. There exists $β_0(q,η)$ such that, for every inverse temperature $β\geβ_0$, the zero-field $q$-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time $\exp(O(k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) Fix $Δ\ge 3$. On $Δ$-regular graphs of girth $g$ in time $\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).$ (b) Bipartite hard-core. Fix $Δ\ge3$ and $η\in(0,1]$. There exists $λ_0(Δ,η)$ such that, for every fugacity $λ\geλ_0$, the hard-core model admits approximate counting and sampling: (i) On $Δ$-regular vertex-transitive bipartite graphs in time $\exp(O (k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) On $Δ$-regular bipartite graphs of girth $g$ in $\exp(O(n e^{- g}))\operatorname{poly}(n,1/\varepsilon).$ All four results follow from verifying the hypotheses of a new framework we call C-3PO. At a high level, the C-3PO algorithm proceeds by enumerating small cuts and reconstructing the original measure through cluster expansions. Underlying the algorithm is an improvement of subspace enumeration methods via active regression.
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
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.