Metraipolis › archive › dc_5388ca7baa61

The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth — arXiv:2610.42011

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.42011
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:22.697Z
SHA-256 of the archived text
acb043e8bbc952e0ea247a32b6215ceff747aaa49d0c3ebb75841a0eeda74df6
Stable URL of this page
https://metraipolis.com/documento/dc_5388ca7baa61

How to cite

The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth — arXiv:2610.42011 — arXiv (en), https://arxiv.org/abs/2610.42011 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5388ca7baa61 (Metraipolis archive dc_5388ca7baa61, sha256 acb043e8bbc952e0ea247a32b6215ceff747aaa49d0c3ebb75841a0eeda74df6)
BibTeX
@misc{dc5388ca7baa61,
  title = {The C-3PO Framework: Algorithms for $#mathrmBIS$-Hard Problems on Graphs with Low Threshold Rank or High Girth — arXiv:2610.42011},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42011},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5388ca7baa61; sha256 acb043e8bbc952e0ea247a32b6215ceff747aaa49d0c3ebb75841a0eeda74df6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42011. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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_\eta = k_\eta(G)$ count normalized-Laplacian eigenvalues strictly below $\eta$. 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 $\eta\in(0,1]$. There exists $\beta_0(q,\eta)$ such that, for every inverse temperature $\beta\ge\beta_0$, the zero-field $q$-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time $\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon).$ (ii) Fix $\Delta \ge 3$. On $\Delta$-regular graphs of girth $g$ in time $\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).$ (b) Bipartite hard-core. Fix $\Delta\ge3$ and $\eta\in(0,1]$. There exists $\lambda_0(\Delta,\eta)$ such that, for every fugacity $\lambda\ge\lambda_0$, the hard-core model admits approximate counting and sampling: (i) On $\Delta$-regular vertex-transitive bipartite graphs in time $\exp(O (k_\eta))\operatorname{poly}(n,1/\varepsilon).$ (ii) On $\Delta$-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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2610.42011 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:34:47.025Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).