Name
Abstract | ||
|---|---|---|
The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a condition similar to that of the asymmetric Lov\'asz Local Lemma. When applied 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^{k/2}/k$ for some constant $c>0$. If in addition the hypergraph is linear, the condition can be weaken to $d\le c\cdot 2^{k}/k^2$ for some constant $c>0$, matching the rapid mixing condition for Glauber dynamics in Hermon, Sly and Zhang [HSZ19]. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.4230/LIPICS.ICALP.2022.103 | International Colloquium on Automata, Languages and Programming (ICALP) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoliang Qiu | 1 | 0 | 0.34 |
| Yanheng Wang | 2 | 0 | 0.68 |
| Chihao Zhang | 3 | 0 | 0.68 |