Document Open Access Logo

Fast Algorithms for General Spin Systems on Bipartite Expanders

Authors Andreas Galanis, Leslie Ann Goldberg, James Stewart

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.37.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
James Stewart
  • Department of Computer Science, University of Oxford, UK

Cite AsGet BibTex

Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast Algorithms for General Spin Systems on Bipartite Expanders. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.37

Abstract

A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander Δ-regular graphs, including the canonical class of bipartite random Δ-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Our approach generalises the techniques of Jenssen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to "bicliques" of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in Õ(n²) time, where n is the size of the graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Discrete mathematics
Keywords
  • bipartite expanders
  • approximate counting
  • spin systems

Metrics

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

Related Versions

  • A full version with all proofs can be found at https://arxiv.org/abs/2004.13442. The theorem numbers here match those in the full version. Proof sketches here refer to lemmas in the full version without restating them in detail.

References

  1. N. Alon. Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory. Combinatorica, 6(3):207-219, 1986. Google Scholar
  2. N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72(1-3):15-19, 1988. Google Scholar
  3. G. Brito, I. Dumitriu, and K. D. Harris. Spectral gap in random bipartite biregular graphs and applications. arXiv:1804.07808, 2018. Google Scholar
  4. A. Bulatov and M. Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2):148-186, 2005. Google Scholar
  5. J.-Y. Cai, A. Galanis, L. A. Goldberg, H. Guo, M. Jerrum, D. Štefankovič, and E. Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690-711, 2016. Google Scholar
  6. S. Cannon and W. Perkins. Counting independent sets in unbalanced bipartite graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1456-1466. SIAM, 2020. Google Scholar
  7. C. Carlson, E. Davies, and A. Kolla. Efficient algorithms for the Potts model on small-set expanders. CoRR, abs/2003.01154, 2020. Google Scholar
  8. Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda. Fast algorithms at low temperatures via Markov chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1-41:14, 2019. Google Scholar
  9. S. De Winter, J. Schillewaert, and J. Verstraete. Large incidence-free sets in geometries. The electronic journal of Combinatorics, 19(4):P24, 2012. Google Scholar
  10. M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3‐4):260-289, 2000. Google Scholar
  11. M. E. Dyer, L. A. Goldberg, C. S. Greenhill, and M. Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2004. Google Scholar
  12. J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. CoRR, cs.DM/0405020, 2004. Google Scholar
  13. A. Galanis, L. A. Goldberg, and M. Jerrum. Approximately counting H-colorings is #BIS-hard. SIAM Journal on Computing, 45(3):680-711, 2016. Google Scholar
  14. A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6), 2015. Google Scholar
  15. A. Galanis, D. Štefankovič, E. Vigoda, and L. Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. Google Scholar
  16. L. A. Goldberg and M. Jerrum. Approximating the partition function of the ferromagnetic Potts model. J. ACM, 59(5), 2012. Google Scholar
  17. L. A. Goldberg, S. Kelk, and M. Paterson. The complexity of choosing an H-coloring (nearly) uniformly at random. SIAM Journal on Computing, 33(2):416-432, 2004. Google Scholar
  18. A. Govorov, J.-Y. Cai, and M. Dyer. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. arXiv:2002.02021, 2020. Google Scholar
  19. C. Gruber and H. Kunz. General properties of polymer systems. Communications in Mathematical Physics, 22(2):133-161, 1971. Google Scholar
  20. W. H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its applications, 226(228):593-616, 1995. Google Scholar
  21. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. Probability Theory and Related Fields, pages 1-45, 2019. Google Scholar
  22. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  23. M. Jenssen, P. Keevash, and W. Perkins. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 2235-2247, 2019. Google Scholar
  24. N. Kahale. Eigenvalues and expansion of regular graphs. J. ACM, 42(5):1091–1106, 1995. URL: https://doi.org/10.1145/210118.210136.
  25. C. Liao, J. Lin, P. Lu, and Z. Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:12, 2019. Google Scholar
  26. A. Sly and N. Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, November 2014. Google Scholar
  27. R. M. Tanner. Explicit concentrators from generalized N-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287-293, 1984. 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