Caltech Logo

CMI Seminar: Jingcheng Liu

Tuesday, October 8, 2019
4:00pm to 5:00pm
Add to Cal
Annenberg 314
Uniform Sampling Through the Lovász Local Lemma
Jingcheng Liu, Postdoc, Center for the Mathematics of Information, Caltech,

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.

For more information, please contact Linda Taddeo by phone at 626-395-6704 or by email at [email protected] or visit Mathematics of Information Seminar - Upcoming Events.