Rapid Mixing from Spectral Independence beyond the Boolean Domain
Rapid Mixing from Spectral Independence beyond the Boolean Domain
复制标题
布尔域之外的光谱独立性的快速混合
DOI：
10.1145/3531008
复制
发表时间：
2020-07
影响因子：
1.3
通讯作者：
Chihao Zhang
中科院分区：
文献类型：
--
作者：
Weiming Feng;Heng Guo;Yitong Yin;Chihao Zhang
我们将谱独立性的概念(由Anari，Liu和Oveis Gharan[4]引入)从布尔域推广到一般的离散域。这一性质描述了关联有限的分布，并暗示相应的Glauber动力学是快速混合的。作为一个具体的应用，我们证明了抽样适当的q-染色的Glauber动力学对于具有最大度Δ的无三角形图族在多项式时间内混合，其中≥(α*+δ)Δ1.763是α*≈*=exp(1/α*)的唯一解，而δ？0是任意常数。这是第一个在可能无界Δ的情况下采样适当Q-着色的有效算法。我们建立光谱独立性的主要工具是Goldberg、Martin和Paterson的递归耦合[25]。
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [4]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q≥ (α* + δ)Δ where α*≈ 1.763 is the unique solution to α* = exp (1/α*) and δ Þ 0 is any constant. This is the first efficient algorithm for sampling proper q-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [25].
登录
查看更多内容
DOI：
10.1007/1-4020-2721-4_1
发表时间：
2011-04
期刊：
--
影响因子：
--
作者：
B. Ya
通讯作者：
B. Ya
DOI：
10.1137/1.9781611976465.94
发表时间：
2020-07
期刊：
--
影响因子：
--
作者：
Zongchen Chen;Andreas Galanis;Daniel Stefankovic;Eric Vigoda
通讯作者：
Zongchen Chen;Andreas Galanis;Daniel Stefankovic;Eric Vigoda
DOI：
10.1214/105051606000000330
发表时间：
2005-01
期刊：
--
影响因子：
--
作者：
Thomas P. Hayes;Eric Vigoda
通讯作者：
Thomas P. Hayes;Eric Vigoda
DOI：
10.1109/focs.2019.00085
发表时间：
2019-06
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
通讯作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
影响因子：
1.6
作者：
J. Salas;A. Sokal
通讯作者：
J. Salas;A. Sokal