Document Open Access Logo

Approximating Observables Is as Hard as Counting

Authors Andreas Galanis, Daniel Štefankovič, Eric Vigoda

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.63.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Daniel Štefankovič
  • Department of Computer Science, Univerity of Rochester, NY, USA
Eric Vigoda
  • Department of Computer Science, University of California Santa Barbara, CA, USA

Funding

  • Štefankovič, Daniel: supported by NSF grant CCF-2007287.
  • Vigoda, Eric: supported by NSF CCF-2007022.

Cite AsGet BibTex

Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Approximating Observables Is as Hard as Counting. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 63:1-63:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.63

Abstract

We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph. A recent work of Galanis et al (2021) established NP-hardness of approximating the average size of an independent set utilizing hardness of the corresponding optimization problem and the related phase transition behavior. We instead consider settings where the underlying optimization problem is easily solvable. Our main contribution is to classify the complexity of approximating a wide class of observables via a generic reduction from approximate counting to the problem of estimating local observables. The key idea is to use the observables to interpolate the counting problem. Using this new approach, we are able to study observables on bipartite graphs where the underlying optimization problem is easy but the counting problem is believed to be hard. The most-well studied class of graphs that was excluded from previous hardness results were bipartite graphs. We establish hardness for estimating the average size of the independent set in bipartite graphs of maximum degree 6; more generally, we show tight hardness results for general vertex-edge observables for antiferromagnetic 2-spin systems on bipartite graphs. Our techniques go beyond 2-spin systems, and for the ferromagnetic Potts model we establish hardness of approximating the number of monochromatic edges in the same region as known hardness of approximate counting results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Generating random combinatorial structures
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Approximate Counting
  • Averages
  • Phase Transitions
  • Random Structures

Metrics

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

References

  1. R. J. Baxter. Onsager and Kaufman’s calculation of the spontaneous magnetization of the Ising model. Journal of Statistical Physics, 145(3):518-548, 2011. Google Scholar
  2. M. Bordewich, C. Greenhill, and V. Patel. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Structures & Algorithms, 48(1):21-52, 2016. Google Scholar
  3. 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
  4. D. Chelkak and S. Smirnov. Universality in the 2D Ising model and conformal invariance of fermionic observables. Inventiones mathematicae, 189(3):515-580, 2012. Google Scholar
  5. Z. Chen, K. Liu, and E. Vigoda. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1537-1550, 2021. Google Scholar
  6. 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
  7. 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
  8. A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing, 25(4):500-559, 2016. Google Scholar
  9. A. Galanis, D. Štefankovič, and E. Vigoda. The complexity of approximating averages on bounded-degree graphs. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1345-1355, 2020. Google Scholar
  10. 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
  11. L. A. Goldberg and M. Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59(5), 2012. Google Scholar
  12. G. Grimmett. The Random-Cluster Model. In Probability on Discrete Structures, pages 73-123. Springer, 2004. Google Scholar
  13. M. Jerrum and A. Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087-1116, 1993. Google Scholar
  14. M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  15. L. Li, P. Lu, and Y. Yin. Correlation decay up to uniqueness in spin systems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-84, 2013. Google Scholar
  16. L. J. Schulman, A. Sinclair, and P. Srivastava. Symbolic integration and the complexity of computing averages. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1231-1245, 2015. Google Scholar
  17. A. Sinclair and P. Srivastava. Lee-Yang theorems and the complexity of computing averages. Communications in Mathematical Physics, 329(3):827-858, 2014. Google Scholar
  18. A. Sly. Computational transition at the uniqueness threshold. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 287-296, 2010. Google Scholar
  19. A. Sly and N. Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, 2014. Google Scholar
  20. D. Weitz. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 140-149, 2006. 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