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
QIU Guo-liang1, ZHANG Chi-hao2
CLC Number:
[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. |
|