LFCS Seminar: Tuesday 21 October: Xinyuan Zhang | LFCS

Title: Sampling and Counting via Coupling Independence

Abstract: In recent years, the framework of spectral independence has become a

powerful tool for designing efficient algorithms for sampling and

counting problems. In this talk, I will introduce a closely related

concept, called coupling independence, and demonstrate its

applications to both approximate sampling and counting. In

particular, we establish a near-linear time sampler for the

ferromagnetic Ising model with an external field. Furthermore, we

present a deterministic approximate counting algorithm for the

partition functions of spin systems based on coupling independence.

This leads to the first deterministic algorithm that approximately

counts graph colorings in the same regime previously accessible only

to randomized algorithms. Based on joint works with Xiaoyu Chen,

Weiming Feng, Heng Guo, and Zongrui Zou.