Page 190 - 《软件学报》2026年第4期

陈小羽 等: 吉布斯采样在临界点前的快速收敛 1631

54th Annual ACM SIGACT Symp. on Theory of Computing. Rome: ACM, 2022. 1418–1430. [doi: 10.1145/3519935.3520048]
[6] Anari N, Liu KK, Gharan SO. Spectral independence in high-dimensional expanders and applications to the hardcore model. In: Proc. of
the 61st IEEE Annual Symp. on Foundations of Computer Science (FOCS). Durham: IEEE, 2020. 1319–1330. [doi: 10.1109/FOCS46700.
2020.00125]
[7] Chen XY, Feng WM, Yin YT, Zhang XY. Optimal mixing for two-state anti-ferromagnetic spin systems. In: Proc. of the 63rd IEEE
Annual Symp. on Foundations of Computer Science (FOCS). Denver: IEEE, 2022. 588–599. [doi: 10.1109/focs54457.2022.00062]
[8] Chen ZC, Liu KK, Vigoda E. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In: Proc. of the 61st IEEE Annual
Symp. on Foundations of Computer Science (FOCS). Durham: IEEE, 2020. 1307–1318. [doi: 10.1109/FOCS46700.2020.00124]
[9] Chen ZC, Liu KK, Vigoda E. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion. In: Proc. of
the 53rd Annual ACM SIGACT Symp. on Theory of Computing. ACM, 2021. 1537–1550. [doi: 10.1145/3406325.3451035]
[10] Dyer M, Sinclair A, Vigoda E, Weitz D. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures &
Algorithms, 2004, 24(4): 461–479. [doi: 10.1002/rsa.20004]
[11] Efthymiou C, Hayes TP, Štefankovič D, Vigoda E, Yin YT. Convergence of MCMC and loopy BP in the tree uniqueness region for the
hard-core model. SIAM Journal on Computing, 2019, 48(2): 581–643. [doi: 10.1137/17M1127144]
[12] Hayes TP, Vigoda E. Coupling with the stationary distribution and improved sampling for colorings and independent sets. The Annals of
Applied Probability, 2006, 16(3): 1297–1318. [doi: 10.1214/105051606000000330]
[13] Luby M, Vigoda E. Approximately counting up to four (extended abstract). In: Proc. of the 29th Annual ACM Symp. on Theory of
Computing. El Paso: ACM, 1997. 682–687. [doi: 10.1145/258533.258663]
[14] Luby M, Vigoda E. Fast convergence of the Glauber dynamics for sampling independent sets. Random Structures & Algorithms, 1999,
15(3-4): 229–241. [doi: 10.1002/(SICI)1098-2418(199910/12)15:3/4<229::AID-RSA3>3.0.CO;2-X]
[15] Sly A. Computational transition at the uniqueness threshold. In: Proc. of the 51st IEEE Annual Symp. on Foundations of Computer
Science. Las Vegas: IEEE, 2010. 287–296. [doi: 10.1109/FOCS.2010.34]
[16] Vigoda E. A note on the Glauber dynamics for sampling independent sets. The Electronic Journal of Combinatorics, 2001, 8(1): R8. [doi:
10.37236/1552]
[17] Weitz D. Counting independent sets up to the tree threshold. In: Proc. of the 38th Annual ACM Symp. on Theory of Computing. Seattle:
ACM, 2006. 140–149. [doi: 10.1145/1132516.1132538]
[18] Greenhill C. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity,
2000, 9(1): 52–72. [doi: 10.1007/PL00001601]
[19] Valiant LG. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 1979, 8(3): 410–421. [doi: 10.1137/
0208032]
[20] Patel V, Regts G. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal
on Computing, 2017, 46(6): 1893–1919. [doi: 10.1137/16M1101003]
[21] Peters H, Regts G. On a conjecture of Sokal concerning roots of the independence polynomial. Michigan Mathematical Journal, 2019,
68(1): 33–55. [doi: 10.1307/mmj/1541667626]
[22] Jerrum MR, Valiant LG, Vazirani VV. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer
Science, 1986, 43: 169–188. [doi: 10.1016/0304-3975(86)90174-X]
[23] Alev VL, Lau LC. Improved analysis of higher order random walks and applications. In: Proc. of the 52nd Annual ACM SIGACT Symp.
on Theory of Computing. Chicago: ACM, 2020. 1198–1211. [doi: 10.1145/3357713.3384317]
[24] Anari N, Liu KK, Gharan SO, Vinzant C. Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a
matroid. In: Proc. of the 51st Annual ACM SIGACT Symp. on Theory of Computing. Phoenix: ACM, 2019. 1–12. [doi: 10.1145/
3313276.3316385]
[25] Cryan M, Guo H, Mousa G. Modified log-Sobolev inequalities for strongly log-concave distributions. In: Proc. of the 60th IEEE Annual
Symp. on Foundations of Computer Science (FOCS). Baltimore: IEEE, 2019. 1358–1370. [doi: 10.1109/FOCS.2019.00083]
[26] Bubley R, Dyer M. Path coupling: A technique for proving rapid mixing in Markov chains. In: Proc. of the 38th Annual Symp. on
Foundations of Computer Science. Miami Beach: IEEE, 1997. 223–231. [doi: 10.1109/sfcs.1997.646111]
[27] Chen MF. Trilogy of couplings and general formulas for lower bound of spectral gap. In: Accardi L, Heyde CC, eds. Probability Towards
2000. New York: Springer, 1998. 123–136. [doi: 10.1007/978-1-4612-2224-8_7]
[28] Weitz D. Combinatorial criteria for uniqueness of Gibbs measures. Random Structures & Algorithms, 2005, 27(4): 445–475. [doi: 10.
1002/rsa.20073]
[29] Feng WM, Guo H, Yin YT, Zhang CH. Rapid mixing from spectral independence beyond the boolean domain. In: Proc. of the 2021