Caltech Home > PMA Home > Calendar > CMI Seminar: Jingcheng Liu
open search form
Tuesday, October 08, 2019
4:00 PM - 5:00 PM
Annenberg 314

CMI Seminar: Jingcheng Liu

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.