CMI Seminar: Jingcheng Liu

Tuesday October 8, 2019 4:00 PM

Uniform Sampling Through the Lovász Local Lemma

Speaker: Jingcheng Liu, Caltech
Location: Annenberg 314

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.

Series Center for the Mathematics of Information (CMI) Seminar Series

Contact: Linda Taddeo at 626-395-6704 ltaddeo@caltech.edu
For more information visit: http://www.cmi.caltech.edu/events.shtml