Sampling Matchings in Near-linear Time
En palabras de los autores
For every fixed activity , we establish three results for the monomer--dimer model on an -vertex simple graph with edges and maximum degree . 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time , giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using work and depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error in work. For dense graphs with , 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.
Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.