Computer Science ›› 2020, Vol. 47 ›› Issue (5): 22-26.doi: 10.11896/jsjkx.200200119

Special Issue: Theoretical Computer Scinece

• Theoretical Computer Science • Previous Articles     Next Articles

Approximability of Partition Functions of Ferromagnetic Two-state Spin Systems

QIU Guo-liang1, ZHANG Chi-hao2   

  1. 1 School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 610000,China
    2 John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 200240,China
  • Received:2020-02-26 Online:2020-05-15 Published:2020-05-19
  • About author:QIU Guo-liang,born in 1996,postgra-duate.His main research interest is theo-retical computer science.
    ZHANG Chi-hao,born in 1988,Ph.D,Ph.D supervisor,is a member of China Computer Federation.His main research interest is theoretical computer science.
  • Supported by:
    This work was supported by the Young Scientists Fund of the National Natural Science Foundation of China (NSFC 61902241).

Abstract: The two-spin system is a simplified model for the interaction of the multiparticle system in statistical physics.Computing the partition function of the system is of great significance in both statistical physics and computer science.It is well-known that the exact computation of the partition function is #P-hard for general systems.Therefore,the approximability of the partition function has attracted a lot of attention of computer scientists.Notable progress has been made along this line of research in recent years.Close connections between the approximability of the partition function and the phase transition of the physical mo-dels have been revealed.Based on these connections,approximation algorithms have been discovered for the model in a wide range of parameters.This paper reviews the research on the approximability of the partition functions of ferromagnetic 2-spin systems,introduces the main ideas of three classes of algorithms for this problem,including MCMC based algorithms,decay of correlation based algorithm and recent polynomial interpolation based algorithms.Moreover,the results of these algorithms are compared with the current inapproximability results.

Key words: Approximate counting, Partition function of ferromagnetic two-state spin systems, Sampling

CLC Number: 

  • TP301
[1]BULATOV A,GROHE M.The Complexity of Partition Functions[J].Theoretical Computer Science,2004,348(2/3):148-186.
[2]WEITZ D.Counting independent sets up to the tree threshold[C]//Proceeding of the 38th Annual ACM Symposium on Theo-ry of Computing.2006:140-149.
[3]LI L,LU P Y,YIN Y T.Correlation decay up to uniqueness in spin systems[C]//Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.2013:67-84.
[4]SLY A,SUN N.The computational hardness of counting in two-spin models on d-regular graphs[C]//53rd Annual IEEE Symposium on Foundations of Computer Science.2012:361-369.
[5]SINCLAIR A,SRIVASTAVA P,THURLEY M.Approxima-tion Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs[J].Journal of Statistical Phy-sics,2014,155(4):666-686.
[6]JERRUM M,VALIANT L G,VAZIRANI V V.Random genera-tion of combinatorial structures from a uniform distribution[J].Theoretical Computer Science,1986,43:169-188.
[7]LEVIN D,PERES Y.Markov Chains and Mixing Times[M].American Mathematical Society,2017.
[8]MOSSEL E,SLY A.Exact threshold for Ising-Gibbs samplerson general graphs[J].The Annals of Probability,2013,41(1):294-328.
[9]LIU J C,LU P Y,ZHANG C H.The complexity of ferromagnetic two-spin systems with external fields[C]//Proceedings of RANDOM.2014:843-856.
[10]GOLDBERG A L,JERRUM M,PATERSON M.The computational complexity of two-state spin systems[J].Random Structures & Algorithms,2003,23(2):133-154.
[11]JERRUM M,SINCLAIR A.Polynomial-time approximation algorithms for the Ising model[C]// International Colloquium on Automata,Languages & Programming.Springer-Verlag,1990.
[12]GAMARNIK D,KATZ D.Correlation decay and deterministic FPTAS for counting colorings of a graph[J].Journal of Discrete Algorithms,2012,12:29-47.
[13]GUO H,LU P Y.Uniqueness,spatial mixing,and approxima-tion for ferromagnetic 2-spin systems[J].TOCT,2018,10(4):17:1-17:25.
[14]BARVINOK A.Combinatorics and Complexity of PartitionFunctions[M].Springer International Publishing,2016.
[15]PATEL V,REGTS G.Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials[J].SIAM Journal on Computing,2017,46(6):1893-1919.
[16]SCOTT A D,SOKAL A D.The Repulsive Lattice Gas,the Independent-Set Polynomial,and the Lovász Local Lemma[J].Journal of Statistical Physics,2005,118(5/6):1151-1261.
[17]PETERS H,REGTS G.On a conjecture of sokal concerningroots of the independence polynomial[J].The Michigan Mathematical Journal,2019,68(1):33-55.
[18]SOKAL A.A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models[J].Markov Process,2001(1):21-38.
[19]LIU J C,SINCLAIR A,SRIVASTAVA P.A deterministic algorithm for counting colorings with 2-delta colors[C]//60th IEEE Annual Symposium on Foundations of Computer Science.2019:1380-1404.
[20]ASANO T.Theorems on the partition functions of the Heisenberg ferromagnets[J].The Physical Society of Japan,1970,29:350-359.
[21]RUELLE DAVID.Extension of the lee-yang circle theorem[J].Physical Review Letters,1971,26:303-304.
[22]GUO H,LIAO C,LU P Y,et al.Zeros of Holant problems:locations and algorithms[C]//Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms.2019:2262-2278.
[23]GUO H,LIU J C,LU P Y.Zeros of ferromagnetic 2-spin systems[C]// Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms.2020:181-192.
[24]GEORGII H O.Gibbs Measures and Phase Transitions(2nd Edition)[M].Berlin:Springer,2011.
[25]DYER M,GOLDBERG L A,GREENHILL C,et al.The Relative Complexity of Approximate Counting Problems[J].Algorithmica,2004,38(3):471-500.
[1] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[2] LIANG Yi-wen, DU Yu-song. Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao [J]. Computer Science, 2022, 49(6A): 485-489.
[3] HOU Xia-ye, CHEN Hai-yan, ZHANG Bing, YUAN Li-gang, JIA Yi-zhen. Active Metric Learning Based on Support Vector Machines [J]. Computer Science, 2022, 49(6A): 113-118.
[4] ZHANG Jia-neng, LI Hui, WU Hao-lin, WANG Zhuang. Exploration and Exploitation Balanced Experience Replay [J]. Computer Science, 2022, 49(5): 179-185.
[5] JIANG Hao-chen, WEI Zi-qi, LIU Lin, CHEN Jun. Imbalanced Data Classification:A Survey and Experiments in Medical Domain [J]. Computer Science, 2022, 49(1): 80-88.
[6] HUANG Ying-qi, CHEN Hong-mei. Cost-sensitive Convolutional Neural Network Based Hybrid Method for Imbalanced Data Classification [J]. Computer Science, 2021, 48(9): 77-85.
[7] ZHANG Ren-jie, CHEN Wei, HANG Meng-xin, WU Li-fa. Detection of Abnormal Flow of Imbalanced Samples Based on Variational Autoencoder [J]. Computer Science, 2021, 48(7): 62-69.
[8] ZHENG Jian-hua, LI Xiao-min, LIU Shuang-yin, LI Di. Improved Random Forest Imbalance Data Classification Algorithm Combining Cascaded Up-sampling and Down-sampling [J]. Computer Science, 2021, 48(7): 145-154.
[9] QIAN Xin-yuan, WU Wen-yuan. Identity-based Encryption Scheme Based on R-SIS/R-LWE [J]. Computer Science, 2021, 48(6): 315-323.
[10] HUAN Wen-ming, LIN Hai-tao. Design of Intrusion Detection System Based on Sampling Ensemble Algorithm [J]. Computer Science, 2021, 48(11A): 705-712.
[11] LUO Yue-tong, JIANG Pei-feng, DUAN Chang, ZHOU Bo. Small Object Detection Oriented Improved-RetinaNet Model and Its Application [J]. Computer Science, 2021, 48(10): 233-238.
[12] OUYANG Peng, LU Lu, ZHANG Fan-long, QIU Shao-jian. Cross-project Clone Consistency Prediction via Transfer Learning and Oversampling Technology [J]. Computer Science, 2020, 47(9): 10-16.
[13] XIE Wen-kang, FAN Wei-bei, ZHANG Yu-jie, XU He, LI Peng. ENLHS:Sampling Approach to Auto Tuning Kafka Configurations [J]. Computer Science, 2020, 47(8): 119-126.
[14] ZHANG De-gan, FAN Hong-rui, GONG Chang-le, GAO Jin-xin, ZHANG Ting, ZHAO Peng-zhen and CHEN Chen. New Method of Data Missing Estimation for Vehicle Traffic Based on Tensor [J]. Computer Science, 2020, 47(6A): 505-511.
[15] TIAN Wei, LIU Hao, CHEN Gen-long, GONG Xiao-hui. Cross Subset-guided Adaptive Measurement for Block Compressive Sensing [J]. Computer Science, 2020, 47(12): 190-196.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!