Document Open Access Logo

FPTAS for Hardcore and Ising Models on Hypergraphs

Authors Pinyan Lu, Kuan Yang, Chihao Zhang

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.51.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Pinyan Lu
Kuan Yang
Chihao Zhang

Cite AsGet BibTex

Pinyan Lu, Kuan Yang, and Chihao Zhang. FPTAS for Hardcore and Ising Models on Hypergraphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.51

Abstract

Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic physics which connects microscopic particles and their interactions with their macroscopic and statistical properties of materials such as energy, entropy, ferromagnetism, etc. If each local interaction of the system involves only two particles, the system can be described by a graph. In this case, fully polynomial-time approximation scheme (FPTAS) for computing the partition function of both hardcore and anti-ferromagnetic Ising model was designed up to the uniqueness condition of the system. These result are the best possible since approximately computing the partition function beyond this threshold is NP-hard. In this paper, we generalize these results to general physics systems, where each local interaction may involves multiple particles. Such systems are described by hypergraphs. For hardcore model, we also provide FPTAS up to the uniqueness condition, and for anti-ferromagnetic Ising model, we obtain FPTAS under a slightly stronger condition.
Keywords
  • hard-core model
  • ising model
  • hypergraph
  • spatial mixing
  • correlation decay

Metrics

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

References

  1. Antar Bandyopadhyay and David Gamarnik. Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Structures &Algorithms, 33(4):452-479, 2008. Google Scholar
  2. Magnus Bordewich, Martin Dyer, and Marek Karpinski. Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Structures &Algorithms, 32(3):375-399, 2008. URL: http://dx.doi.org/10.1002/rsa.20204.
  3. Martin Dyer, Mark Jerrum, and Eric Vigoda. Rapidly mixing Markov chains for dismantleable constraint graphs. In Randomization and Approximation Techniques in Computer Science, pages 68-77. Springer, 2002. Google Scholar
  4. Martin E. Dyer, Alan M. Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM Jounal on Computing, 31(5):1527-1541, 2002. URL: http://epubs.siam.org/sam-bin/dbq/article/38384.
  5. Martin E. Dyer and Catherine S. Greenhill. On Markov chains for independent sets. Journal of Algorithms, 35(1):17-49, 2000. Google Scholar
  6. A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Arxiv preprint arXiv:1203.2226, 2012. Google Scholar
  7. David Gamarnik and Dmitriy Katz. Correlation decay and deterministic FPTAS for counting colorings of a graph. Journal of Discrete Algorithms, 12:29-47, 2012. Google Scholar
  8. Leslie Ann Goldberg and Mark Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. SIAM Journal on Computing, 42(3):1132-1157, 2013. Google Scholar
  9. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures &Algorithms, 7(2):157-166, 1995. Google Scholar
  10. Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087-1116, 1993. Google Scholar
  11. Mark Jerrum and Alistair Sinclair. The Markov chain monte carlo method: an approach to approximate counting and integration. Approximation algorithms for NP-hard problems, pages 482-520, 1996. Google Scholar
  12. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51:671-697, July 2004. URL: http://dx.doi.org/10.1145/1008731.1008738.
  13. Liang Li, Pinyan Lu, and Yitong Yin. Approximate counting via correlation decay in spin systems. In Proceedings of the 23th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12), pages 922-940. SIAM, 2012. Google Scholar
  14. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pages 67-84. SIAM, 2013. Google Scholar
  15. Chengyu Lin, Jingcheng Liu, and Pinyan Lu. A simple FPTAS for counting edge covers. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 341-348, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.25.
  16. Jingcheng Liu and Pinyan Lu. FPTAS for #BIS with degree bounds on one side. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC'15), 2015. Google Scholar
  17. Jingcheng Liu and Pinyan Lu. FPTAS for counting monotone CNF. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 1531-1548, 2015. Google Scholar
  18. Jingcheng Liu, Pinyan Lu, and Chihao Zhang. FPTAS for counting weighted edge covers. In In Proceedings of the 22nd European Symposium on Algorithms (ESA'14), pages 654-665, 2014. Google Scholar
  19. Pinyan Lu, Menghui Wang, and Chihao Zhang. FPTAS for weighted Fibonacci gates and its applications. Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), pages 787-799, 2014. Google Scholar
  20. Pinyan Lu and Yitong Yin. Improved FPTAS for multi-spin systems. In Proceedings of APPROX-RANDOM, pages 639-654. Springer, 2013. Google Scholar
  21. Michael Luby and Eric Vigoda. Approximately counting up to four. In Proceedings of the 29th Annual ACM Symposium on Theory of computing (STOC'97), pages 682-687. ACM, 1997. Google Scholar
  22. Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, and Linji Yang. Improved mixing condition on the grid for counting and sampling independent sets. Probability Theory and Related Fields, 156(1-2):75-99, 2013. Google Scholar
  23. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics, 155(4):666-686, 2014. Google Scholar
  24. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), pages 361-369. IEEE, 2012. Google Scholar
  25. Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000. Google Scholar
  26. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), pages 140-149. ACM, 2006. Google Scholar
  27. Yitong Yin and Jinman Zhao. Counting hypergraph matchings up to uniqueness threshold. arXiv preprint arXiv:1503.05812, 2015. 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 Imprint Privacy Contact