A Perfect Sampler for Hypergraph Independent Sets

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\'asz Local Lemma. When specialized to $d$-regular $k$-uniform hypergraphs on $n$ vertices, our sampler terminates in expected $O(n\log n)$ time provided $d\le c\cdot 2^{\frac{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.