3

A Counting Lovász Local Lemma
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying …
Hongyang Liu, Chunyang Wang, Yitong Yin, Yiyao Zhang, Can Zhou
PDF Cite arXiv
Approximate Colorwise Tensorization of Entropy and Optimal Mixing of the Wang-Swendsen-Kotecký Dynamics
We study the mixing time of Wang-Swendsen-Kotecký (WSK) dynamics for uniformly sampling proper $q$-colorings. The WSK dynamics is …
Chunyang Wang, Yuichi Yoshida, Zihan Zhang
PDF Cite arXiv