CMI Seminar: Jingcheng Liu

We propose a new algorithmic framework, called partial rejection sampling, to draw samples exactly from a product distribution conditioned on avoiding a set of bad events. Our framework builds new connections between the variable framework of the Lovász Local Lemma and some classical sampling algorithms such as the cycle-popping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample (weighted) independent sets, and satisfying assignments of k-CNF formulas with bounded variable occurrences.
Based on joint work with Heng Guo and Mark Jerrum.