Metraipolis › archive › dc_720e794857ba
Sampling Matchings in Near-linear Time — arXiv:2609.21936
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.21936
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T02:46:11.341Z
- SHA-256 of the archived text
2c538ab22b0b0ea195d83ba5da38cb3ac1a63059ec068d9f1ce9df8f5db2f45c- Stable URL of this page
https://metraipolis.com/documento/dc_720e794857ba
How to cite
Sampling Matchings in Near-linear Time — arXiv:2609.21936 — arXiv (en), https://arxiv.org/abs/2609.21936 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_720e794857ba (Metraipolis archive dc_720e794857ba, sha256 2c538ab22b0b0ea195d83ba5da38cb3ac1a63059ec068d9f1ce9df8f5db2f45c)
BibTeX
@misc{dc720e794857ba,
title = {Sampling Matchings in Near-linear Time — arXiv:2609.21936},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.21936},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_720e794857ba; sha256 2c538ab22b0b0ea195d83ba5da38cb3ac1a63059ec068d9f1ce9df8f5db2f45c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21936. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For every fixed activity $\lambda>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $\Delta$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_\lambda(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_\lambda(m+n)$ work and $\tilde{O}_\lambda(\min\{\Delta,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_\lambda(n^2/\varepsilon^2)$ work. For dense graphs with $m=\Theta(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.21936 — 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-10-10T02:29:43.012Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).