Rapid mixing from spectral independence beyond the Boolean domain

Weiming Feng; Heng Guo; Yitong Yin; Chihao Zhang

Rapid mixing from spectral independence beyond the Boolean domain

Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) 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 푞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 푞 ≥ (α* + δ)Δ where α* ≈ 1.763 is the unique solution to α* = exp(1/α*) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper 푞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].

Original language	English
Title of host publication	Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21)
Publisher	ACM
Pages	1558 – 1577
Number of pages	20
ISBN (Print)	9781611976465
Publication status	Published - 10 Jan 2021
Event	ACM-SIAM Symposium on Discrete Algorithms - Virtual event Duration: 10 Jan 2021 → 13 Jan 2021 https://www.siam.org/conferences/cm/conference/soda21

Symposium

Symposium	ACM-SIAM Symposium on Discrete Algorithms
Abbreviated title	SODA 21
City	Virtual event
Period	10/01/21 → 13/01/21
Internet address	https://www.siam.org/conferences/cm/conference/soda21

Access to Document

Rapid mixing from_FENG_DOA30092020_AFVAccepted author manuscript, 260 KBLicence: All Rights Reserved

https://dl.acm.org/doi/abs/10.5555/3458064.3458159Licence: All Rights Reserved

New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@inproceedings{5b6313303957474cbb22b9c02895afe4,

title = "Rapid mixing from spectral independence beyond the Boolean domain",

abstract = "We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) 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 푞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 푞 ≥ (α* + δ)Δ where α* ≈ 1.763 is the unique solution to α* = exp(1/α*) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper 푞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].",

author = "Weiming Feng and Heng Guo and Yitong Yin and Chihao Zhang",

year = "2021",

month = jan,

day = "10",

language = "English",

isbn = "9781611976465",

pages = "1558 – 1577",

booktitle = "Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21)",

publisher = "ACM",

note = "ACM-SIAM Symposium on Discrete Algorithms, SODA 21 ; Conference date: 10-01-2021 Through 13-01-2021",

url = "https://www.siam.org/conferences/cm/conference/soda21",

}

TY - GEN

T1 - Rapid mixing from spectral independence beyond the Boolean domain

AU - Feng, Weiming

AU - Guo, Heng

AU - Yin, Yitong

AU - Zhang, Chihao

PY - 2021/1/10

Y1 - 2021/1/10

N2 - We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) 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 푞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 푞 ≥ (α* + δ)Δ where α* ≈ 1.763 is the unique solution to α* = exp(1/α*) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper 푞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].

AB - We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) 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 푞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 푞 ≥ (α* + δ)Δ where α* ≈ 1.763 is the unique solution to α* = exp(1/α*) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper 푞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].

M3 - Conference contribution

SN - 9781611976465

SP - 1558

EP - 1577

BT - Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21)

PB - ACM

T2 - ACM-SIAM Symposium on Discrete Algorithms

Y2 - 10 January 2021 through 13 January 2021

ER -

Rapid mixing from spectral independence beyond the Boolean domain

Abstract

Symposium

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this