A Perfect Sampler for Hypergraph Independent Sets

05/04/2022

∙

by   Guoliang Qiu, et al.

∙

0

∙

share

The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a similar condition to the asymmetric Lovász Local Lemma. When specialized to d-regular k-uniform hypergraphs on n vertices, our sampler terminates in expected O(nlog n) time provided d≤ c· 2^k/2 where c>0 is a constant, matching the rapid mixing condition for Glauber dynamics in [HSZ19]. The analysis of our algorithm is simple and clean.