More Web Proxy on the site http://driver.im/

research-article

Zeros of holant problems: locations and algorithms

Authors:

Chihao ZhangAuthors Info & Claims

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 2262 - 2278

Published: 06 January 2019 Publication History

Abstract

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second order recurrence modulo a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by 2-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting. We also use the "winding" technique to deduce the second result on cubic graphs.

References

[1]

{Asa70} Taro Asano. Theorems on the partition functions of the Heisenberg ferromagnets. J. Phys. Soc. Japan, 29:350--359, 1970. 3

[2]

{Bac18} Miriam Backens. A complete dichotomy for complex-valued Holant<sup>c</sup>. In ICALP, volume 107 of LIPIcs, pages 12:1--12:14, 2018. 1

[3]

{Bar16} Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and combinatorics. Springer, 2016. 2, 4, 5

[4]

{BGK+07} Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, and Prasad Tetali. Simple deterministic approximation algorithms for counting matchings. In STOC, pages 122--127, 2007. 15

Digital Library

[5]

{Bul13} Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1--34:41, 2013. 1

Digital Library

[6]

{CC17} Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1--19:39, 2017. 1, 9

Digital Library

[7]

{CGW16} Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput., 45(5): 1671--1728, 2016. 1, 12, 15

[8]

{CLX11} Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of Holant problems. SIAM J. Comput., 40(4):1101--1132, 2011. 1, 7

Digital Library

[9]

{CLX18} Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real Holant<sup>c</sup> problems. In SODA, pages 1802--1821, 2018. 1

Digital Library

[10]

{DGGJ04} Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471{-500, 2004. 12

[11]

{DGL<sup>+</sup> 12} Jan Draisma, Dion C. Gijswijt, László Lovász, Guus Regts, and Alexander Schrijver. Characterizing partition functions of the vertex model. J. Algebra, 350:197--206, 2012. 1

[12]

{DJM17} Martin E. Dyer, Mark Jerrum, and Haiko Müller. On the switch Markov chain for perfect matchings. J. ACM, 64(2):12:1--12:33, 2017. 2

Digital Library

[13]

{DR13} Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3): 1245--1274, 2013. 1

[14]

{FLS07} Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc., 20(1):37--51, 2007. 1

[15]

{GJP03} Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random Struct. Algorithms, 23(2):133--154, 2003. 2

[16]

{Gra02} John H. Grace. The zeros of a polynomial. Proc. Camb. Philos. Soc, 11:352--357, 1902. 3

[17]

{GŠV16} Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Comb. Probab. Comput., 25(4):500--559, 2016. 2

[18]

{HLZ16} Lingxiao Huang, Pinyan Lu, and Chihao Zhang. Canonical paths for MCMC: from art to science. In SODA, pages 514--527, 2016. 2, 3, 15, 16

Digital Library

[19]

{JS89} Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149--1178, 1989. 2

Digital Library

[20]

{JS93} Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087--1116, 1993. 2, 9, 15

Digital Library

[21]

{JSV04} Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671{-697, 2004. 2

Digital Library

[22]

{JVV86} Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci., 43:169--188, 1986. 16

Digital Library

[23]

{LLL14} Chengyu Lin, Jingcheng Liu, and Pinyan Lu. A simple FPTAS for counting edge covers. In SODA, pages 341--348, 2014. 2, 15

Digital Library

[24]

{LLY13} Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In SODA, pages 67--84, 2013. 2

Digital Library

[25]

{LSS17} Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The Ising partition function: Zeros and deterministic approximation. In FOCS, pages 986--997, 2017. 3

[26]

{LW18} Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. Siam J. Comput., 47(3):798--828, 2018. 1

[27]

{LWZ14} Pinyan Lu, Menghui Wang, and Chihao Zhang. FPTAS for weighted Fibonacci gates and its applications. In ICALP, pages 787--799, 2014. 2

[28]

{McQ13} Colin McQuillan. Approximating Holant problems by winding. CoRR, abs/1301.2880, 2013. 2, 3, 15, 16

[29]

{PR17a} Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput., 46(6):1893--1919, 2017. 2, 6, 15

[30]

{PR17b} Han Peters and Guus Regts. On a conjecture of Sokal concerning roots of the independence polynomial. CoRR, abs/1701.08049, 2017. To appear in Mich. Math. J. 3

[31]

{Rue71} David Ruelle. Extension of the Lee-Yang circle theorem. Phys. Rev. Lett., 26:303--304, 1971. 2, 3

[32]

{Rue99a} David Ruelle. Counting unbranched subgraphs. J. Algebraic Combin., 9(2): 157--160, 1999. 2, 3

Digital Library

[33]

{Rue99b} David Ruelle. Zeros of graph-counting polynomials. Comm. Math. Phys., 200(1):43--56, 1999. 2, 3

[34]

{Sch13} Alexander Schrijver. Characterizing partition functions of the spin model by rank growth. Indag. Math. (N.S.), 24(4):1018--1023, 2013. 1

[35]

{SS14} Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383--2416, 2014. 2

[36]

{SST14} Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. J. Stat. Phys., 155(4):666--686, 2014. 2

[37]

{ŠVW18} Daniel Štefankovič, Eric Vigoda, and John Wilmes. On counting perfect matchings in general graphs. In LATIN, pages 873--885, 2018. 2

[38]

{Sze22} Gábor Szegő. Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen. Math. Z., 13(1):28--55, 1922. 3

[39]

{Val08} Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565--1594, 2008. 1, 2, 7

Digital Library

[40]

{Wal22} Joseph L. Walsh. On the location of the roots of certain types of polynomials. Trans. Amer. Math. Soc., 24(3):163--180, 1922. 3

Cited By

Buys PGalanis APatel VRegts GMarx D(2021)Lee-yang zeros and the complexity of the ferromagnetic ising model on bounded-degree graphsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458155(1508-1519)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458155

Zeros of holant problems: locations and algorithms
1. Theory of computation

Recommendations

Zeros of Holant Problems: Locations and Algorithms

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second-order recurrence modulo in a couple of exceptional cases. As a ...
Dichotomy theorems for holant problems
A Dichotomy for Real Weighted Holant Problems

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2019

2993 pages

Program Chair:
Timothy M. Chan
University of Illinois at Urbana-Champaign

Sponsors

SIAM Activity Group on Discrete Mathematics

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2019

Check for updates

Qualifiers

Research-article

Conference

SODA '19

Sponsor:

SODA '19: Symposium on Discrete Algorithms

January 6 - 9, 2019

California, San Diego

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
52
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Buys PGalanis APatel VRegts GMarx D(2021)Lee-yang zeros and the complexity of the ferromagnetic ising model on bounded-degree graphsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458155(1508-1519)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458155

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents