Document Open Access Logo

A Perfect Sampler for Hypergraph Independent Sets

Authors Guoliang Qiu, Yanheng Wang, Chihao Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.103.pdf
  • Filesize: 0.9 MB
  • 16 pages

Document Identifiers

Author Details

Guoliang Qiu
  • Shanghai Jiao Tong University, China
Yanheng Wang
  • ETH Zürich, Switzerland
Chihao Zhang
  • Shanghai Jiao Tong University, China

Funding

  • Zhang, Chihao: The author is supported by National Natural Science Foundation of China Grant 61902241.

Cite As Get BibTex

Guoliang Qiu, Yanheng Wang, and Chihao Zhang. A Perfect Sampler for Hypergraph Independent Sets. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 103:1-103:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.103

Abstract

The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a similar condition of the asymmetric Lovász 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 ≤ c⋅ 2^{k/2} where c > 0 is a constant, matching the rapid mixing condition for Glauber dynamics in Hermon, Sly and Zhang [Hermon et al., 2019]. The analysis of our algorithm is simple and clean.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Coupling from the past
  • Markov chains
  • Hypergraph independent sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic. Approximation via correlation decay when strong spatial mixing fails. SIAM Journal on Computing, 48(2):279-349, 2019. Google Scholar
  2. Weiming Feng, Heng Guo, and Jiaheng Wang. Improved bounds for randomly colouring simple hypergraphs. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.05554.
  3. Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Fast sampling and counting k-sat solutions in the local lemma regime. Journal of the ACM, 68(6):40:1-40:42, 2021. Google Scholar
  4. Weiming Feng, Kun He, and Yitong Yin. Sampling constraint satisfaction solutions in the local lemma regime. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1565-1578, 2021. Google Scholar
  5. Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang. Counting solutions to random cnf formulas. SIAM Journal on Computing, 50(6):1701-1738, 2021. Google Scholar
  6. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lovász local lemma. Journal of the ACM, 66(3):1-31, 2019. Google Scholar
  7. Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang. Counting hypergraph colorings in the local lemma regime. SIAM Journal on Computing, 48(4):1397-1424, 2019. Google Scholar
  8. Kun He, Xiaoming Sun, and Kewen Wu. Perfect sampling for (atomic) Lovász local lemma. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.03932.
  9. Kun He, Chunyang Wang, and Yitong Yin. Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time. arXiv preprint, 2022. URL: http://arxiv.org/abs/2204.01520.
  10. Jonathan Hermon, Allan Sly, and Yumeng Zhang. Rapid mixing of hypergraph independent sets. Random Structures & Algorithms, 54(4):730-767, 2019. Google Scholar
  11. Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. On the sampling Lovász local lemma for atomic constraint satisfaction problems. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.08342.
  12. Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong. Towards the sampling Lovász local lemma. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021. Google Scholar
  13. Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  14. Eyal Lubetzky and Allan Sly. Information percolation and cutoff for the stochastic ising model. Journal of the American Mathematical Society, 29(3):729-774, 2016. Google Scholar
  15. Ankur Moitra. Approximate counting, the Lovász local lemma, and inference in graphical models. Journal of the ACM, 66(2):10:1-10:25, 2019. Google Scholar
  16. Robin A Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. Journal of the ACM, 57(2):1-15, 2010. Google Scholar
  17. James Gary Propp and David Bruce Wilson. Exact sampling with coupled markov chains and applications to statistical mechanics. Random Structures & Algorithms, 9(1-2):223-252, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact